AcWing 3719. 畅通工程
原题链接
简单
作者:
史一帆
,
2022-01-02 08:40:36
,
所有人可见
,
阅读 215
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
for (int i = 1; i < N; i ++ )
p[i] = i;
int n, m;
cin >> n >> m;
while (m -- )
{
int x, y;
cin >> x >> y;
int fa = find(x), fb = find(y);
if (fa != fb)
p[fa] = fb;
}
int res = 0;
for (int i = 1; i <= n; i ++ )
if (p[i] == i)
res ++ ;
cout << res - 1 << endl;
return 0;
}