Cod sursa(job #1146662)

Utilizator iarbaCrestez Paul iarba Data 19 martie 2014 10:37:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
using namespace std;
int st[100001],sf[100001],next[400001],dest[400001],cc[100001];
int poz,n,m,c,i,x,y;
void add(int x, int y)
{
	if(st[x]==0){st[x]=poz;}
	else{next[sf[x]]=poz;}
	sf[x]=poz;
	dest[poz]=y;
	next[poz]=0;
}
void conex(int nod)
{
	cc[nod]=c;int j;
	for(j=st[nod];j;j=next[j]){
		if(cc[dest[j]]==0){conex(dest[j]);}
							  }
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%ld%ld",&x,&y);
		poz++;add(x,y);
		poz++;add(y,x);
					 }
	for(i=1;i<=n;i++){
		if(cc[i]==0){c++;conex(i);}
					 }
	printf("%ld",c);
return 0;
}