Cod sursa(job #631676)

Utilizator Marius96Marius Gavrilescu Marius96 Data 9 noiembrie 2011 15:41:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<cstdio>
#include<vector>
#undef XYZZY
using namespace std;
vector<int> v[100005];
int         s[100005];
int nr;

void dfs(int x){
	if(s[x])return;
	s[x]=nr;
	for(int i=0;i<v[x].size();i++)
		dfs(v[x][i]);
}

int main(){
	#ifndef XYZZY
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	#endif
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);x--;y--;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=0;i<n;i++){
		if(s[i])continue;
		nr++;
		dfs(i);
	}
	printf("%d\n",nr);
	#ifdef XYZZY
	for(int i=0;i<n;i++)
		printf("%d\n",s[i]);
	#endif
	return 0;
}