Cod sursa(job #1463669)

Utilizator Tester01tester Tester01 Data 21 iulie 2015 14:35:23
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#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("disjoint.in");
 ofstream cout("disjoint.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;
}