Cod sursa(job #1715356)

Utilizator Mihai7Gheoace Mihai Mihai7 Data 10 iunie 2016 13:59:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<cstdio>
#include<bitset>
#include<cstdlib>
using namespace std;
bitset < 100001 > viz;

typedef struct nod{
	int a;
	nod* urm;
} *Pnod;
Pnod v[100001];
void Push(Pnod &dest,int val)
{
	Pnod p;
	p=new nod;
	p -> a=val;
	p -> urm = dest;
	dest = p;
}
void dfs(int i)
{
	Pnod p;
	viz[i]=1;
	for(p=v[i];p!=NULL;p=p->urm)
		if(!viz[p->a])
			dfs(p->a);
}
int main()
{
	int n,m,x,y,cnt=0,i;
	FILE *f=freopen("dfs.in","r",stdin),
	*g=freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=0;i<m;++i)
	{
		scanf("%d %d",&x,&y);
		Push(v[x],y);
		Push(v[y],x);
	}
	for( i=1;i<=n;++i)
	{
		if(viz[i]==0)
		{
			++cnt;
			dfs(i);
		}
	}
	printf("%d\n",cnt);
}