Cod sursa(job #710715)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 10 martie 2012 16:54:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>

using namespace std;

#define nmax 101000

class graf{
	

public:
	
	vector<int> adj[nmax];
	
	void add(int a, int b);
};

void graf::add(int a, int b){
	
	adj[a].push_back(b);
	adj[b].push_back(a);
}

	

graf G;
int N,M,a,b,nr;
int viz[nmax];

void dfs(int nod){
	
	if (viz[nod])
		return ;
	viz[nod]=1;
	
	vector<int> :: iterator it;
	
	for (it=G.adj[nod].begin();it!=G.adj[nod].end();++it) 
		   if (!viz[*it])
			   dfs(*it);
}

int main(){
	
	int i;
	
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d %d", &N, &M);
	while(M--){

		scanf("%d %d", &a, &b);
		G.add(a,b);
	}
	
	nr=0;
	
	for (i=1;i<=N;++i)
		 if (!viz[i]){
			 nr++;
			 dfs(i);
		 }
		 
	printf("%d\n", nr);

	return 0;
}