Cod sursa(job #800540)

Utilizator SovStoStoicescu Mihail Cristian SovSto Data 21 octombrie 2012 21:33:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <iostream>
using namespace std;

int n,m,viz[100005],k;

typedef struct nod
{
	int x;
	nod *a;
}*pNod;
pNod v[100005];

void add(pNod &dest,int val)
{
	pNod p;
	p=new nod;
	p->x=val;
	p->a=dest;
	dest=p;
}

void citire()
{	
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i,x,y;
	for(i=1;i<=m;i++)
		{
			scanf("%d %d",&x,&y);
				add(v[x],y);
				add(v[y],x);
		}
}
	
	
	



void DFS(int nod)
{
	viz[nod]=1;
	pNod p;
	for(p=v[nod];p!=NULL;p=p->a)
	{
		if(!viz[p->x])DFS(p->x);
	}
}

int main()
{	citire();
	int i;
	for(i=1;i<=n;i++)
		if(viz[i]==0)
		{
			k++;
			DFS(i);
		}
	printf("%d",k);
	return 0;
	
}