Pagini recente » Cod sursa (job #900802) | Cod sursa (job #1161730) | Cod sursa (job #2063506) | Cod sursa (job #1919988) | Cod sursa (job #2847939)
#include <iostream>
#include <fstream>
#include <unordered_map>
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
const int DIM = 100001;
int n, m;
int parent[DIM], rang[DIM];
int Find(int x)
{
if (x != parent[x])
{
parent[x] = Find(parent[x]);
}
return parent[x];
}
void Union(int x, int y)
{
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY)
{
if (rang[rootX] > rang[rootY])
{
parent[rootY] = rootX;
}
else
{
parent[rootX] = rootY;
if (rang[rootX] == rang[rootY])
{
rang[rootY]++;
}
}
}
}
void Read()
{
f >> n >> m;
for (int i = 1; i <= n; i++)
{
parent[i] = i;
}
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
Union(x, y);
}
}
void Print()
{
unordered_map <int, int> U_M;
for (int i = 1; i <= n; i++)
{
U_M[Find(i)] = 1;
}
g << U_M.size();
}
int main()
{
Read();
Print();
}