Cod sursa(job #627352)

Utilizator paul24090FMI - Balauru Paul paul24090 Data 29 octombrie 2011 17:36:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <list>

using namespace std;

int n,m,nr=0;
int v[100002];
list<int> l[100002];
list<int>::iterator it;

void citire()
{
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		l[x].push_back(y);
		l[y].push_back(x);
	}
}

void afisare()
{
	/*for(int i=1;i<=n;i++)
	{
		printf("%d: ",i);
		for(it=l[i].begin();it!=l[i].end();++it)
			printf("%d ",*it);
		printf("\n");
	}*/
	printf("%d\n",nr);
}

void dfs(int k)
{
	v[k]=1;
	list<int>::iterator it;
	for(it=l[k].begin();it!=l[k].end();++it)
		if(v[*it]==0)
			dfs(*it);
}

int main()
{
	freopen("dfs.in","rt",stdin);
	freopen("dfs.out","wt",stdout);
	citire();
	for(int i=1;i<=n;i++)
		if(v[i]==0)
		{
			dfs(i);
			nr++;
		}
	afisare();
	return 0;
}