Pagini recente » Cod sursa (job #1132671) | Cod sursa (job #892989) | Cod sursa (job #1593315) | Cod sursa (job #2968410) | Cod sursa (job #2834051)
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
int m, n;
int parent[100001], rang[100001];
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 >> m >> n;
for (int i = 1; i <= m; i++)
{
parent[i] = i;
}
for (int i = 1; i <= n; i++)
{
int x, y;
f >> x >> y;
Union(x, y);
}
}
int main()
{
Read();
set <int> Set;
for (int i = 1; i <= m; i++)
{
Set.insert(Find(i));
}
g << Set.size();
}