求某社交网络中共有 n 个人,即a1,a2,…,an。当给定 n,以及部分人际关系。为扩展人际关系,可利用已有的人际关系来认识一些不识之人,若只通过一人的牵线,试问哪些人员之间可间接建立起人际关系。 算法: 输入描述: n, (a1, a2), (a1, a3), …, (ai, aj) 例如,5, (1, 2), (1, 3), (1, 4), (2, 5), (3, 4) 输出描述:(ai,aj)…(ak, al) 要求:各括号对的输出要求保证按按字典序或自然数递增排序。
时间: 2023-08-18 21:07:02 浏览: 47
以下是C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<pair<int,int>>& res) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
res.push_back({min(u, v), max(u, v)});
dfs(v, graph, visited, res);
}
}
}
int main() {
int n;
cin >> n;
vector<vector<int>> graph(n+1);
vector<bool> visited(n+1, false);
vector<pair<int,int>> res;
int a, b;
while (cin >> a >> b) {
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i, graph, visited, res);
}
}
sort(res.begin(), res.end());
for (auto p : res) {
cout << '(' << p.first << ',' << p.second << ')' << endl;
}
return 0;
}
```
输入格式为:
```
n
a1 b1
a2 b2
...
an bn
```
其中 n 表示人员数量,后面的 ai 和 bi 表示两个人之间存在人际关系。输出的格式为:
```
(ai,aj)...(ak,al)
```
表示这些人之间存在间接人际关系,且按字典序或自然数递增排序。