Pagini recente » Cod sursa (job #1722041) | Cod sursa (job #2672566) | Cod sursa (job #2899500) | Cod sursa (job #1009813) | Cod sursa (job #2582224)
#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;
}