Cod sursa(job #1431054)

Utilizator andy94Andrei Ursache andy94 Data 8 mai 2015 23:18:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<vector>

#define NR_NEIG 200

using namespace std;

struct Node {
	int id;
	Node* next;
};

void add_neigh(Node* &node, int id) {
	Node* n = new Node();
	n->id = id;
	n->next = node;
	node = n;
}

void dfs(Node* nodes[], bool visited[], int i) {

	visited[i] = true;
	Node* it = nodes[i];

	while (it != NULL) {
		if (!visited[it->id]) {
			dfs(nodes, visited, it->id);

		}
		it = it->next;
	}

}

int main() {

	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	int n, m;
	scanf("%d %d", &n, &m);

	int id1, id2;

	Node* nodes[n + 1];
	bool visited[n + 1];

	for (int i = 1; i <= n; ++i) {
		nodes[i] = NULL;
		visited[i] = false;
	}

	for (int i = 0; i < m; ++i) {
		scanf("%d %d", &id1, &id2);

		add_neigh(nodes[id1], id2);
		add_neigh(nodes[id2], id1);
	}

	int ctc_no = 0;

	for (int i = 1; i <= n; ++i) {
		if (!visited[i]) {
			dfs(nodes, visited, i);
			ctc_no++;
		}
	}

	printf("%d", ctc_no);

	fclose(stdin);
	fclose(stdout);

	return 0;
}