Cod sursa(job #494087)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 20 octombrie 2010 18:37:54
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>

struct nod {
	int inf;
	nod *next;
};
const int maxn=100001,maxm=200001;
int i,n,m,viz[maxn],S=0;
nod *A[maxn];

void add(int x, int y)
{
	nod *q=new nod;
	q->inf=y;
    q->next=A[x];
	A[x]=q;
}

void citire()
{
	int x,y;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
}

void dfs(int p)
{
	nod *x;
	viz[p]=1;
	for(x=A[p];x!=NULL;x=x->next)
		if(viz[x->inf]==0) 
			dfs(x->inf);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	for(i=1;i<=n;i++) viz[i]=0;
	for(i=1;i<=n;i++)
		if(viz[i]==0) 
			{
				dfs(i);
				S++;
		    }
	printf("%d",S);
}