Cod sursa(job #1720188)

Utilizator MIrcea_GheoaceGheoace Mircea MIrcea_Gheoace Data 21 iunie 2016 18:34:01
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
# include<cstdio>
using namespace std;
# define nmax 100000
int N,M;
typedef struct nod
{
	int x;
	nod *a;
}*pNod;
pNod A[nmax];bool viz[nmax];
void add(pNod &adr,int val)
{
	pNod p;
	p=new nod;
	p->x=val;
	p->a=adr;
	adr=p;
}
void citire()
{
	FILE *f=freopen("dfs.in","r",stdin),*g=freopen("dfs.out","w",stdout);
	scanf("%d%d",&N,&M);
	int x,y;
	for(int i=1;i<=M;++i)
	{
		scanf("%d%d",&x,&y);
		add(A[x],y);
		add(A[y],x);
	}
}
void dfs(int start)
{
	viz[start]=1;
	pNod p;
	for(p=A[start];p!=NULL;p=p->a)if(!viz[p->x])dfs(p->x);
}
int main()
{
	citire();
	int cnt=0,i;
	for(i=1;i<=N;++i)
		if(!viz[i])
		{
			cnt++;
			dfs(i);
		}
	printf("%d",cnt);
}