Cod sursa(job #2582224)

Utilizator DawlauAndrei Blahovici Dawlau Data 16 martie 2020 15:21:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int VMAX = 1e5;

vector <int> dad;
vector <int> level;

int V, E;

int Find(int node) {

	int root = node;
	for (; root != dad[root]; root = dad[root]);

	while (root != node) {

		int auxNode = node;
		node = dad[node];
		dad[auxNode] = root;
	}

	return root;
}

void Unite(int node1, int node2) {

	if (level[node1] > level[node2])
		dad[node2] = node1;
	else dad[node1] = node2;

	if (level[node1] == level[node2])
		++level[node2];
}

void readData() {

	fin >> V >> E;

	dad.resize(1 + V);
	level.resize(1 + V);

	for (int node = 1; node <= V; ++node) {

		dad[node] = node;
		level[node] = 1;
	}

	for (; E; --E) {

		int from, to;
		fin >> from >> to;

		int root1 = Find(from);
		int root2 = Find(to);

		if (root1 != root2)
			Unite(root1, root2);
	}
}

int main() {

	readData();

	int CC = 0;
	for (int node = 1; node <= V; ++node)
		if (dad[node] == node)
			++CC;

	fout << CC;
}