简答题
偏难
#7476
社交网络(2023.12) 随着社交平台的兴起,人们之间的沟通变得越来越密切。通过Facebook的分享功能,只要你是对方的好友,你就可以转发对方的状态,并且你…
社交网络(2023.12)
随着社交平台的兴起,人们之间的沟通变得越来越密切。通过Facebook的分享功能,只要你是对方的好友,你就可以转发对方的状态,并且你的名字将出现在“转发链”上。经过若干次转发以后,很可能A分享了一条好友C的状态,而C的这条状态实际上是分享B的,但A与B可能并不是好友,即A通过C间接分享了B的状态。
给定你N个人之间的好友关系,好友关系一定是双向的。只要两个人是好友,他们就可以互相转发对方的状态,无论这条状态是他自己的,还是他转发了其他人的。现在请你统计,对于每两个人,他们是否有可能间接转发对方的状态。
时间限制:1000
内存限制:262144
输入
第一行1个整数N(1<=N<=300)。 接下来N行每行N个整数,表示一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人是好友,0则表示不是好友。 保证矩阵的主对角线上都是1,并且矩阵关于主对角线对称。
输出
一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人可能间接转发对方的状态,0则表示不可能。
样例输入
5 11000 11100 01100 00011 00011
样例输出
11100 11100 11100 00011 00011
提示
在输入数据中,1与2是好友,2与3是好友,4与5是好友。 因此1、2、3有可能互相转发状态;4、5有可能互相转发状态。这两组人之间则不可能。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int n, fa[310];
char a[310][310];
int find(int x) {
if (x == fa[x]) {
return x;
}
return find(fa[x]);
}
void merge(int x, int y) {
if (find(x) == find(y)) {
return;
}
fa[find(x)] = find(y);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == 49 && i != j) {
merge(i, j);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (find(i) == find(j)) {
cout << 1;
} else {
cout << 0;
}
}
cout << '\n';
}
}</pre>
这道题暂未补解析。