Pagini recente » Cod sursa (job #824093) | Cod sursa (job #912670) | Cod sursa (job #1463671)
#include <bits/stdc++.h>
using namespace std;
#define Nmax 100013
int n,m,op,a,b;
class DisjointForest{
private :
int father[Nmax];
int find(int node){
if (node == father[node]) return node;
return father[node] = find(father[node]);
}
public :
int components;
DisjointForest(int n) {components=n; for (int i=1;i<=n;++i) father[i]=i; };
void merge(int a,int b){
int fa = find(a);
int fb = find(b);
father[fa]=fb;
}
bool check (int a,int b){
if (find(a)==find(b)) return 0;
return 1;
}
};
int main(void) {
ifstream cin("dfs.in");
ofstream cout("dfs.out");
cin>>n>>m;
DisjointForest Forest(n);
while(m--){
cin>>a>>b;
Forest.components-=Forest.check(a,b);
Forest.merge(a,b);
}
cout<<Forest.components;
return 0;
}