算法日志 46 day 图论（并查集）

标题：冗余连接

   108. 冗余连接 (kamacoder.com)
  标题形貌
有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

先请你找出冗余边，删除后，使该图可以重新变成一棵树。
输入形貌
第一行包含一个整数 N，表示图的节点个数和边的个数。
后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。
输出形貌
输出一条可以删除的边。假如有多个答案，请删除标准输入中最后出现的那条边。
 标题分析：

        首先明白并查集办理的问题是两个数是否在同一个聚集中，也可以让两个数到场一个聚集。
        标题要求删除冗余边，冗余边是怎么产生的呢？是两个结点都连着一个结点之后，这两个结点也相连了，这么一看，我们只需要判断，两个结点在不在同一个聚集中，假如在的话，新到场的边是不是就是冗余边了呢。
以是，这一题也是并查集的问题，看看代码

1. #include<iostream>
2. #include<vector>
4. using namespace std;
6. int n;
7. vector<int> father(1001,0);
9. void init(){
10.     for(int i=0;i<=n;i++){
11.         father[i]=i;
12.     }
13. }
15. int find(int u){
16.     return u==father[u]?u:father[u]=find(father[u]);
17. }
19. void join(int u,int v){
20.     u=find(u);
21.     v=find(v);
22.     if(u==v) return;
23.     father[v]=u;
24. }
26. bool isSame(int u,int v){
27.     u=find(u);
28.     v=find(v);
29.     if(u==v) return true;
30.     return false;
31. }
34. int main(){
35.     int s,t;
36.     cin>>n;
37.     init();//初始化
38.     for(int i=0;i<n;i++){
39.         cin>>s>>t;
40.         if(isSame(s,t)){
41.             cout << s << " " << t << endl;
42.             return 0;
43.         }
44.         else{
45.             join(s,t);
46.         }
47.     }
48.      
49.      
50. }

复制代码

标题：冗余连接 2

   109. 冗余连接II (kamacoder.com)
  标题形貌
有一种有向树,该树只有一个根节点，全部其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图： 

现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。
输入形貌
第一行输入一个整数 N，表示有向图中节点和边的个数。 
后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边
输出形貌
输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。
标题分析：

        差别于之前的无向图连接，这次换成了有向图，相比于无向图来说，有向图冗余边的判断就较为复杂。
 情况一：
假如我们找到入度为2的点，那么删一条指向该节点的边就行了。
如图：

找到了节点3 的入度为2，删 1 -> 3 或者 2 -> 3 。选择删次序靠后便可。
但 入度为2 还有一种情况，情况二，只能删特定的一条边，如图：

节点3 的入度为 2，但在删除边的时候，只能删 这条边（节点1 -> 节点3），假如删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（由于找不到根节点）。
综上，假如发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。假如是删哪个都可以，优先删次序靠后的边。
情况三： 假如没有入度为2的点，阐明 图中有环了（注意是有向环）。
如图：

对于情况三，删掉构成环的边就可以了。
既然要对入度举行分析，那么我们就需要对每一边的入度举行统计了

1.     int s, t;
2.     vector<vector<int>> edges;
3.     cin >> n;
4.     vector<int> inDegree(n + 1, 0); // 记录节点入度
5.     for (int i = 0; i < n; i++) {
6.         cin >> s >> t;
7.         inDegree[t]++;
8.         edges.push_back({s, t});
9.     }

复制代码

 那么在统计完成之后，就需要找到入度为2的结点，标题要求删除最后一条边，以是我们倒序遍历即可。

1. vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
2. // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
3. for (int i = n - 1; i >= 0; i--) {
4.     if (inDegree[edges[i][1]] == 2) {
5.         vec.push_back(i);
6.     }
7. }
8. if (vec.size() > 0) {
9.     // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
10.     if (isTreeAfterRemoveEdge(edges, vec[0])) {
11.         cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
12.     } else {
13.         cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
14.     }
15.     return 0;
16. }

复制代码

再来看情况3，没有入度为2 的结点，但是也构成了环，那么删撤除构成环的边，我们单独写一个函数来移除这一条边。
以是总的来说就是两个主要的函数，

• isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树
  
• getRemoveEdge() 确定图中一定有了有向环，那么要找到需要删除的那条边
  

isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树： 将全部边的两端节点分别到场并查集，遇到要 要删除的边则跳过，假如遇到即将到场并查集的边的两端节点 本来就在并查集了，阐明构成了环。
假如顺利将全部边的两端节点（除了要删除的边）到场了并查集，则阐明 删除该条边 还是一个有向树
getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边： 将全部边的两端节点分别到场并查集，假如遇到即将到场并查集的边的两端节点 本来就在并查集了，阐明构成了环。
来看看代码

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. int n;
5. vector<int> father (1001, 0);
6. // 并查集初始化
7. void init() {
8.     for (int i = 1; i <= n; ++i) {
9.         father[i] = i;
10.     }
11. }
12. // 并查集里寻根的过程
13. int find(int u) {
14.     return u == father[u] ? u : father[u] = find(father[u]);
15. }
16. // 将v->u 这条边加入并查集
17. void join(int u, int v) {
18.     u = find(u);
19.     v = find(v);
20.     if (u == v) return ;
21.     father[v] = u;
22. }
23. // 判断 u 和 v是否找到同一个根
24. bool same(int u, int v) {
25.     u = find(u);
26.     v = find(v);
27.     return u == v;
28. }
30. // 在有向图里找到删除的那条边，使其变成树
31. void getRemoveEdge(const vector<vector<int>>& edges) {
32.     init(); // 初始化并查集
33.     for (int i = 0; i < n; i++) { // 遍历所有的边
34.         if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
35.             cout << edges[i][0] << " " << edges[i][1];
36.             return;
37.         } else {
38.             join(edges[i][0], edges[i][1]);
39.         }
40.     }
41. }
43. // 删一条边之后判断是不是树
44. bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
45.     init(); // 初始化并查集
46.     for (int i = 0; i < n; i++) {
47.         if (i == deleteEdge) continue;
48.         if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
49.             return false;
50.         }
51.         join(edges[i][0], edges[i][1]);
52.     }
53.     return true;
54. }
56. int main() {
57.     int s, t;
58.     vector<vector<int>> edges;//存储所有边的信息
59.     cin >> n;
60.     vector<int> inDegree(n + 1, 0); // 记录节点入度
61.     for (int i = 0; i < n; i++) {
62.         cin >> s >> t;
63.         inDegree[t]++;
64.         edges.push_back({s, t});
65.     }
67.     vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
68.     // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
69.     for (int i = n - 1; i >= 0; i--) {
70.         if (inDegree[edges[i][1]] == 2) {
71.             vec.push_back(i);
72.         }
73.     }
74.     // 情况一、情况二
75.     if (vec.size() > 0) {
76.         // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
77.         if (isTreeAfterRemoveEdge(edges, vec[0])) {
78.             cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
79.         } else {
80.             cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
81.         }
82.         return 0;
83.     }
85.     // 处理情况三
86.     // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
87.     getRemoveEdge(edges);
88. }

复制代码

 
对于更具体的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)
已刷标题：141


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。