Cod sursa(job #662844)

Utilizator paul24090FMI - Balauru Paul paul24090 Data 17 ianuarie 2012 01:34:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <list>

using namespace std;

int n,m,s;
int c[100002],v[100002];

list<int> l[100002];

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

void bfs(int s)
{
	c[1]=s;
	v[s]=1;
	int p,u;
	p=1;u=1;
	while(p<=u)
	{
		list<int>::iterator itl;
		for(itl=l[c[p]].begin();itl!=l[c[p]].end();++itl)
			if(v[*itl]==0)
			{
				u++;
				c[u]=*itl;
				v[*itl]=1;
			}
		p++;
	}
}

int main()
{
	freopen("dfs.in","rt",stdin);
	freopen("dfs.out","wt",stdout);
	
	scanf("%d %d", &n, &m);
	citire();
	int nrComp=0;
	for(int i=1;i<=n;i++)
		if(v[i]==0)
		{
			nrComp++;
			bfs(i);
		}
	printf("%d\n",nrComp);
	return 0;
}