Cod sursa(job #338716)

Utilizator prdianaProdan Diana prdiana Data 6 august 2009 18:29:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <queue>
#include <vector>
#define MAXN 100002

using namespace std;

queue<int> q;
vector<int> g[MAXN];
bool viz[MAXN];

void bfs(int s)
{
	int i;
	q.push(s);
	viz[s] = true;
	while (!q.empty())
	{
		for (i=0;i<g[q.front()].size();i++)
		{
			if (!viz[g[q.front()][i]])
			{
				q.push(g[q.front()][i]);
				viz[g[q.front()][i]] = true;
			}
		}
		q.pop();
	}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	int i,n,m,x,y,nrc = 0;

	scanf("%d%d",&n,&m);
	
	for (i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	for (i=1;i<=n;i++)
	{
		if (!viz[i])
		{
			bfs(i);
			nrc++;
		}
	}

	printf("%d\n",nrc);

	return 0;
}