Cod sursa(job #238775)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 3 ianuarie 2009 11:50:30
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#define N 100000
#define FIN "dfs.in"
#define FOUT "dfs.out"
int *a[N];
int x[N],y[N],d[N],n,m,viz[N],rez;
void read()
{
	int i;
	freopen(FIN,"r",stdin);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		++d[x[i]];
		++d[y[i]];
	}
	for (i=1;i<=n;++i)
	{
		a[i]=new int[d[i]++];
		a[i][0]=0;
	}
	for (i=1;i<=m;++i)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		a[y[i]][++a[y[i]][0]]=x[i];
	}
}
void df(int x)
{
	int i;
	viz[x]=1;
	for (i=1;i<=a[x][0];++i)
		if (!viz[a[x][i]])
			df(a[x][i]);
}
void solve()
{
	int i;
	for (i=1;i<=n;++i)
		if (!viz[i])
		{
			df(i);
			++rez;
		}
}
void write()
{
	freopen(FOUT,"w",stdout);
	printf("%d\n",rez);
}
int main()
{
	read();
	solve();
	write();
}