Cod sursa(job #631679)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 9 noiembrie 2011 15:52:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
# include <cstdio>
# include <vector>
using namespace std;

vector<int> v[100001];
char fr[100001];
int c=0;

void dfs (int nod)
{
	//printf ("nod:%d componenta:%d\n",nod,c);
	fr[nod]=1;
	for (int i=0;i<v[nod].size();i++)
		if (!fr[v[nod][i]])
			dfs(v[nod][i]);
}

int main ()
{
	freopen("dfs.in","r",stdin);
	freopen ("dfs.out","w",stdout);
	int n,m,a,b;
	scanf ("%d%d",&n,&m);;
	for (int i=1;i<=m;i++)
	{
		scanf ("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i=1; i<=n;i++)
		if (!fr[i])
		{
			c++;
			dfs(i);
		}
	printf ("%d",c);
	return 0;
}