Cod sursa(job #655693)

Utilizator danirotRotaru Daniel danirot Data 3 ianuarie 2012 12:54:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
int n,m,viz[100001],con;
typedef struct nod
{
	int inf;
	nod *ad;
} *Nod;
Nod a[100001];
void citire()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i,j,k;
    Nod v;
    for(i=1;i<=m;i++)
    {
		scanf("%d %d" ,&j,&k);
		v=new nod;
		v->inf=j;
		v->ad=a[k];
		a[k]=v;
		v=new nod;
		v->inf=k;
		v->ad=a[j];
		a[j]=v;
		
	}
}
void dfs(int n)
{
	Nod v;
	viz[n]=1;
	for(v=a[n];v!=NULL;v=v->ad)
	 if(!viz[v->inf])
	  dfs(v->inf);
}
int main()
{
	citire();
	int i;
	for(i=1;i<=n;i++)
	 if(viz[i]==NULL)
	 {
			con++;dfs(i);
		}
		printf("%d\n",con);
		return 0;
	}