Cod sursa(job #526890)

Utilizator Gaby_mMititelu Gabriel Gaby_m Data 29 ianuarie 2011 18:46:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<queue>
using namespace std;

struct list {
	int neigh;
	list *next;
};

list *listad[100001];
bool viz[100001];
int N, M;
void readData() {
	
	scanf("%d %d", &N, &M);
	int x, y;
	for (int i = 0; i < M; i++) {
		scanf("%d %d ", &x, &y);

		list *aux = new list;
		aux->neigh = y;
		aux->next = listad[x];
		listad[x] = aux;

		aux = new list;
		aux->neigh = x;
		aux->next = listad[y];
		listad[y] = aux;
	}
}

void bfs(int source){
	queue<int> neigh;
	viz[source] = 1;
	neigh.push(source);

	int current;
	list *aux;
	while (!neigh.empty()){
		current = neigh.front();
		neigh.pop();

		aux = listad[current];
		while (aux) {
			if (!viz[aux->neigh]) {
				viz[aux->neigh] = 1;
				neigh.push(aux->neigh);
			}
			aux = aux->next;
		}
	}
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	readData();

	int compconex = 0;

	for (int i = 1; i <= N; i++) {
		if (!viz[i]) {
			compconex++;
			bfs(i);
		}
	}

	printf("%d\n",compconex);
	return 0;
}