Cod sursa(job #362801)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 11 noiembrie 2009 00:20:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

#define N 100000

vector<int> g[N + 1];
int n, m, c;

queue<int> q;
int d[N + 1];

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

void bfs(int s)
{
	int e;
	d[s] = 1;
	q.push(s);
	vector<int> :: iterator i;
	while(!q.empty())
	{
		e = q.front();
		q.pop();
		for(i = g[e].begin(); i != g[e].end(); ++i)
		{
			if(d[*i] == 0)
			{
				d[*i] = 1;
				q.push(*i);
			}
		}
	}
}

void scrie()
{
	printf("%d\n", c);
}

void det_componente()
{
	int k;
	for(k = 1; k <= n; ++k) 
	{
		if(d[k] == 0)
		{
			bfs(k);
			c++;
		}
	}
}

int main()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	citeste();
	det_componente();
	scrie();
	
	return 0;
}