Cod sursa(job #790907)

Utilizator mihaiSimuSimu Mihai mihaiSimu Data 22 septembrie 2012 16:54:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;
bitset<100004> viz;
vector< vector<int> >G;
void dfs(int n){
	viz[n]=1;
	for(int i=0;i<G[n].size();i++){
		if(!viz[G[n][i]])
			dfs(G[n][i]);
	}
}

int main(){
	int n,m;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&m);
	int x,y;
	for(int i=0;i<=n;i++){viz[i]=0; vector<int> vg; G.push_back(vg);}

	for(int i=0;i<m;i++){
		scanf("%d",&x);scanf("%d",&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	int nrc=0;
	for(int i=1;i<=n;i++) 
		if(!viz[i])
		{	nrc++;
			dfs(i);
		}		
	printf("%d",nrc);
	return 0;
}