代码随想录算法训练营第 56 天 |108冗余连接 109冗余连接 II

代码随想录算法训练营

Day56 代码随想录算法训练营第 56 天 |108冗余连接 109冗余连接 II

前言

108冗余连接

讲解文档

109冗余连接 II

讲解文档

一、108冗余连接

1.题目链接

108冗余连接

2.思路

（1）思路：遍历所有边，删除成环的边
（2）判断成环：如果边的两个端点在并查集中有公共祖先，则成环
（3）如果边的两个端点在并查集中没有公共祖先，则加入并查集

3.题解

#include <bits/stdc++.h>
using namespace std;
int father[1005];
int find(int u)
{
    if(u==father[u]) return u;
    else {
        father[u]=find(father[u]);
        return father[u];
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        father[i]=i;
    }
    int s;
    int t;
    for(int i=0;i<n;i++)
    {
        
        cin>>s>>t;
        int s_root=find(s);
        int t_root=find(t);
        if(s_root==t_root)
        {
            cout<<s<<" "<<t;
           return 0;
        }
        else{
            father[s_root]=t_root;//把根节点连起来（现在father里都是根节点了）
            //对照并查集模板里面的添加边的逻辑
        }
    }
}

二、109冗余连接 II

1.题目链接

109冗余连接 II

2.思路

（1）有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边
（2）情况
1）有一个节点入度为2：有两个节点指向这个节点
此时，有两条边可能要被删除，但是不确定删除它们中哪一个（二选一）
2）没有节点入度为2，但是形成有向环：删除环里任何一个边都行

（3）思路
1）用二维数组存放边，并且记录被指向的节点有多少入度（被指向多少次）
2）从后向前遍历所有边，将被指向点入度为2的边的编号放进数组
3）第一种情况：存在入度为2的点
① 从后向前考虑指向点入度为2的边，判断第一条边删除以后是不是有向树
② 是：删掉这条边
不是：删掉第二条指向点入度为2的边
③ 如何判断删除一条边以后是不是有向树

• 使用并查集
• 遍历每一条边，如果当前的边是要删除的那一条则跳 过
• • 如果边的起点和终点有共同祖先，则说明成环，不是有向树
• 如果边的起点和终点没有共同祖先，那么加入并查集（用并查集存边的方法）
  4）第二种情况：有向环
  遍历每一条边
  如果边的起点和终点有共同祖先，则说明成环，删掉这条边

3.题解

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>father(1005,0);
std::vector<vector<int>> edge;
vector<int>in_num(1005,0);
int find(int s)
{
    if(s==father[s])return s;
    else {
        father[s]=find(father[s]);
        return father[s];
    }
}
bool is_tree(int del)//del是要删除边的index
{
    for(int i=0;i<n;i++)
    {
        if(i==del)continue;
        int root1=find(edge[i][0]);
        int root2=find(edge[i][1]);
        if(root2==root1){
            return false;
        }
        father[edge[i][1]]=edge[i][0];
    }
     
    return true;
}
int main()
{
     
    cin>>n;
    int s;
    int t;
    for(int i=1;i<=n;i++)
    {
        cin>>s>>t;
        edge.push_back({s,t});
        in_num[t]++;
         
        father[i]=i;//顺便初始化father数组
    }
    vector<int>edgeIndex_with_2_in;//存的是边的编号
    for(int i=n-1;i>=0;i--)//优先删除后输入的
    {
        if(in_num[edge[i][1]]==2){
edgeIndex_with_2_in.push_back(i);
        }
     
    }
    
    //如果有入度为2的节点，有2个边指向入度为2的节点
    //前两种情况，也就是一个节点入度为2
    if(edgeIndex_with_2_in.size())
    {
        int index=edgeIndex_with_2_in[0];
            //如果删除边以后，是树
            //只用一次is_tree 因为这个函数会改变father数组
            //如果第一个不行，那么就删掉第二个
        if(is_tree(index))
        {
            cout<<edge[index][0]<<" "<<edge[index][1];
                
        }else{
            index=edgeIndex_with_2_in[1];
            cout<<edge[index][0]<<" "<<edge[index][1];
        }
        return 0;
         
    }else
    //没有入度为2的节点：有环----和无向图冗余连接一样
    {
        for(int i=0;i<n;i++)
        {
            int root_1=find(edge[i][0]);
            int root_2=find(edge[i][1]);
            if(root_1==root_2){
                cout<<edge[i][0]<<" "<<edge[i][1];
                return 0;
            }
            father[edge[i][1]]=edge[i][0];
        }
    }
}