Cod sursa(job #1719617)

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