Cod sursa(job #551853)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 11 martie 2011 10:47:13
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<cstdio>
using namespace std;

int a[1005][1005],v[1005],viz[1005];

int main ()
{
	int n,m,i,j,x,y,st,dr,nr=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		a[x][y]=1;
		a[y][x]=1;
	}
	nr=0;
	for (i=1; i<=n; i++)
		if (viz[i]==0)
		{
			st=1; dr=1; 
			v[1]=i;
			viz[i]=1;
			while (st<=dr)
			{
				for (j=1; j<=n; j++)
					if (a[v[st]][j]==1 && viz[j]==0)
					{
						v[++dr]=j;
						viz[j]=1;
					}
				st++;
			}
			nr++;
		}
	printf("%d",nr);
	return 0;
}