有一个村子,里面有 N个房屋,已知 1号房屋已经连接到互联网了。为了让其它房屋也能连接到互联网,它们自己拉网线。 Input 第一行输入两个整数 N,M,1≤N,M≤200000,N 表示房屋数量,M表示已经拉好的网线数量。接下来有 M 行,每行两个整数 a,b,表示这两个房屋之间拉了网线。 Output 如果所有房屋都连接到了互联网,那么输出 Connected,否则,按房屋编号递增次序,输出还没有连接到互联网的编号。C++
时间: 2023-03-26 16:01:18 浏览: 59
阿富汗一个村子页.pdf
这是一个计算机科学问题,我可以回答。根据输入的数据,可以使用并查集算法来判断所有房屋是否都连接到了互联网。具体实现可以参考以下代码:
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 200005;
int n, m;
int fa[MAXN];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
merge(a, b);
}
bool connected = true;
for (int i = 2; i <= n; i++) {
if (find(i) != find(1)) {
cout << i << endl;
connected = false;
}
}
if (connected) cout << "Connected" << endl;
return ;
}
如果所有房屋都连接到了互联网,输出 Connected,否则按房屋编号递增次序输出还没有连接到互联网的编号。
阅读全文