Cod sursa(job #148153)

Utilizator a7893Nae Mihai a7893 Data 3 martie 2008 22:35:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#define N 100001
int n,m,*a[N],niv[N],viz[N];
struct vec
{
	int x,y;
}v[N];
void read()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&v[i].x,&v[i].y);
		niv[v[i].x]++;
		niv[v[i].y]++;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=new int[niv[i]+1];
		a[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		a[v[i].x][++a[v[i].x][0]]=v[i].y;
		a[v[i].y][++a[v[i].y][0]]=v[i].x;
	}
}
void df(int nod,int nr)
{
	int i;
	viz[nod]=nr;
	for(i=1;i<=a[nod][0];i++)
		if(!viz[a[nod][i]])
			df(a[nod][i],nr);
}
void solve()
{
	int i,max,nr=1;
	for(i=1;i<=n;i++)
		if(!viz[i])
		{
			df(i,nr);
			nr++;
		}
	max=viz[1];
	for(i=2;i<=n;i++)
		if(viz[i]>max)
			max=viz[i];
	printf("%d\n",max);
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	read();
	solve();
	return 0;
}