Submission #1353435

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

struct UnionFind {
  vector<int> data;
  UnionFind(int v) : data(v, -1) {}
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (size(y) > size(x))
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};

int main() {
	
	int n, m;
	cin >> n >> m;
	UnionFind uni(n+1);
	rep(i, m){
		int a, b;
		cin >> a >> b;
		uni.merge(a, b);
	}
	
	vector<bool> used(n+1);
	int ans = 0;
	REP(i, 1, n+1){
		int parent = uni.root(i);
		if(!used[parent] && parent != i){
			used[parent] = true;
			ans++;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result