nowcoder 牛客练习赛99 E(图特殊情况)

發表於 更新於 分類於 Disqus： 文章字數： 200 所需閱讀時間 ≈ 1 分鐘

比赛总结

https://ac.nowcoder.com/acm/contest/34330/E

考虑存在一个点 其它点仅和它断边

注意sum n很大, 清理按m清理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)

// n(完全图), n-1, <= n-2?
int p2[1000010];

ll n ;
ll m ;
vector<int>uv;

void w(){
  scanf("%lld %lld",&n,&m);
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u] ++ ;
    p2[v] ++ ;
    uv.push_back(u);
    uv.push_back(v);
  }
  // 完全图
  if(m == n*(n-1)/2){
    printf("0\n");
    return ;
  }
  if(m == n*(n-1)/2 - 1){ 
    printf("-1\n");
    return ;
  }
  // 连了4个点 -2
  // 连了3个点 -1
  // sum n 很大
  if(n*(n-1)/2 - m > n){
    printf("-2\n");
    return ;
  }
    rep(i,1,n+1){
      if(p2[i] == n-1 - (n*(n-1)/2 - m)){
        printf("-1\n");
        return ;
      }
    }
  printf("-2\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
      w();
      for(auto u:uv)p2[u] = 0;
      uv = {};
  }
  return 0;
}