Cod sursa(job #464938)

Utilizator alisssiaMititelu Andra alisssia Data 22 iunie 2010 16:53:14
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
using namespace std;
#include<cstdio>
#define nmax 100001
struct nod { int v; nod *next;};
nod *a[nmax];
int n,m,nr,use[nmax];

void add(int i, int j)
{
	nod*p=new nod;
	p->v=j;
	p->next=a[i];
	a[i]=p;
}

void dfs(int i)
{
	use[i]=1;
	for(nod *u=a[i];u;u=u->next)
		if(!use[u->v]) dfs(u->v);
}

int main()
{
	int j,x,y;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(j=0;j<n;j++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(j=1;j<=n;j++)
		if(!use[j]) 
		{
			nr++;
			dfs(j);
		}
	printf("%d\n",nr);
	return 0;
}