Cod sursa(job #664452)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 20 ianuarie 2012 09:29:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
# include <cstdio>
# include <vector>

using namespace std;

vector <int> v[100001];
int fr[100001],n, m,a,b,c;

void dfs(int nod)
{
	fr[nod]=1;
	for (int i=0;i<v[nod].size();i++)
		if (fr[v[nod][i]]==0)
		{
			fr[v[nod][i]]=1;
			dfs(v[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);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		if (fr[i]==0)
		{
			c++;
			dfs (i);
		}
	printf ("%d",c);
	return 0;
}