Submission #39464374

---

Source Code Expand

#include<bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

struct UnionFind {
  vector<int> parent;
  vector<int> size;
  vector<int> edgeCnt;

  UnionFind(int n){
    parent.resize(n);
    size.resize(n);
    edgeCnt.resize(n);
    for(int i = 0; i < n; ++i){
      parent[i] = i;
      size[i] = 1;
      edgeCnt[i] = 0;
    }
  }

  int leader(int x) {
    if(parent[x] == x) return x;
    return parent[x] = leader(parent[x]);
  }

  bool merge(int x, int y) {
    x = leader(x);
    y = leader(y);
    if(x == y){
      edgeCnt[x]++;
      return false;
    }
    if(size[x] < size[y]) swap(x, y);
    parent[y] = x;
    size[x] += size[y];
    edgeCnt[x] += edgeCnt[y] + 1;
    return true;
  }

  bool equalsNumVerticesAndNumEdges(int x){
    return size[leader(x)] == edgeCnt[leader(x)];
  }
};

int main(){
  int N, M;
  cin >> N >> M;
  UnionFind uf(N);
  for(int i = 0; i < M; ++i){
    int u, v;
    cin >> u >> v;
    uf.merge(u-1, v-1);
  }

  // それぞれの連結成分で頂点数と辺数が一致しないものがあればNo
  for(int i = 0; i < N; ++i){
    if(!uf.equalsNumVerticesAndNumEdges(i)){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Submission Info

Judge Result