Cod sursa(job #424355)

Utilizator Teodor94Teodor Plop Teodor94 Data 24 martie 2010 19:39:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<cstdio>

const int N=1<<17;

int n,m;
bool marcat[N];

typedef struct nod
{
	int x;
	nod *a;
} *pNod;

pNod v[N];

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);
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(v[x],y);
		add(v[y],x);
	}
}

void dfs(int nod)
{
	pNod p;
	marcat[nod]=true;
	for (p=v[nod];p!=NULL;p=p->a) 
		if (!marcat[p->x]) 
			dfs(p->x);
}	

int main()
{
	citire();
	int nr=0;
	for (int i=1;i<=n;i++) 
		if (!marcat[i]) 
		{ 
			nr++; 
			dfs(i);
		}
	printf("%d\n",nr);
	return 0;
}