Cod sursa(job #698926)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 29 februarie 2012 16:45:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
# include <cstdio>
# include <vector>

using namespace std;

vector <int>muchie[100001];
int fr[100001];
int n, m, a, b, nrc;

void dfs (int nod)
{
	fr[nod] = 1;
	for (int i = 0; i < muchie[nod].size(); i++)
		if (fr[muchie[nod][i]] == 0)
			dfs ( muchie[nod][i] );
}

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