Cod sursa(job #514589)

Utilizator RaddarDascalu Alexandru Raddar Data 19 decembrie 2010 11:34:54
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <algorithm>
#include <iostream>
using namespace std;
int s[1001],a[1001][1001],n,m,i,q;
void citire()
{
	int u,j;
	cin>>n;
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>u;
		cin>>j;
		a[u][j]=1;
		a[j][j]=1;
	}
}
void df_r(int nod)
{
	int k;
	s[nod]=1;
	for(k=1;k<=n;k++)
		if((a[nod][k]==1)&&(s[k]==0))df_r(k);
}
int main ()
{
	q=0;
	freopen ("dfs.in", "r", stdin);
	freopen("dfs.out","w", stdout);
	citire();
	for(i=1;i<=n;i++)
		if(s[i]==0)
		{
			df_r(i);
			q++;
		}
	cout<<q;
}