目录

1、冗余连接

2、冗余连接II

---

1、冗余连接

题目描述

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

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

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例

3
1 2
2 3
1 3

输出示例

1 3

提示信息

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

数据范围：

1 <= N <= 1000.

思路：这道题比较简单，因为是无向图，所以在并查集的基础上使用isSame函数进行判断即可。

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int> parent(1001, 0);

//初始化并查集的各结点的根
void init(){
    for(int i = 0; i < n; i ++){
        parent[i] = i;
    }
}

//找结点的根
int find(int u){
    return u == parent[u] ? u : parent[u] = find(parent[u]);//路径压缩
}

//比较两结点的根是否相同
bool isSame(int u, int v){
    u = find(u);
    v = find(v);
    return u == v;
}

//将两结点加入并查集
//存在v->u这样一条边
void join(int u, int v){
    u = find(u);
    v = find(v);
    if(u == v) return;
    parent[v] = u;
}

int main(){
    while(cin >> n){
        init();
        int node1, node2;
        for(int i = 0; i < n; i ++){
            cin >> node1 >> node2;
            if(isSame(node1, node2)){
                cout << node1 << " " << node2 << endl;
                return 0;
            }
            join(node1, node2);
        }
    }
}

2、冗余连接II

题目描述

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图： 

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

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。 

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

输入示例

3
1 2
1 3
2 3

输出示例

2 3

提示信息

在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3

数据范围：

1 <= N <= 1000.

 思路：这道题相对于上面的题目来说就稍微复杂一点了。

因为是有向图，所以涉及到结点的入度有关问题。

因为只允许有一个父节点，所以当结点的入度为2时，需要删除其中一条边，这里存在两种情况;

第一种是两条边随便删除哪条都可以，那么依据题意就删除最后输入的那条；

第二种是两条边只能删除特定的边；

当然还存在一种情况，那就是没有结点的入度为2，但是自身存在自环，所以需要删除形成环的边。

这里需要注意在结点入度为2的时候，添加边的时候，遍历顺序是从后往前，这样能保证vec里面的第一个编号是标准输入的相对最后的一条边。

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int> parent(1001, 0);

//初始化各结点的根为自身
void init(){
    for(int i = 0; i < n; i ++){
        parent[i] = i;
    }
}

//寻找结点的根
int find(int u){
    return u == parent[u] ? u : parent[u] = find(parent[u]);//路径压缩
}

//判断两个结点的根是否相同
bool isSame(int u, int v){
    u = find(u);
    v = find(v);
    return u == v;
}

//将v->u这条边加入并查集
void join(int u, int v){
    u = find(u);
    v = find(v);
    if(u == v) return;
    parent[v] = u;
}


bool isTreeAfterRemove(vector<vector<int>> edge, int deleteEdge){
    init();
    for(int i = 0; i < n; i ++){
        if(i == deleteEdge) continue;//遇到删除的边就跳过
        if(isSame(edge[i][0], edge[i][1])) return false;
        join(edge[i][0], edge[i][1]);
    }
    return true;
}

void getRemove(vector<vector<int>> edge){
    init();
    for(int i = 0; i < n; i ++){
        if(isSame(edge[i][0], edge[i][1])){
            cout << edge[i][0] << " " << edge[i][1] << endl;
            return;
        }
        join(edge[i][0], edge[i][1]);
    }
}

int main(){
    while(cin >> n){
        int s, t;
        vector<int> inDegree(n + 1, 0);//计算各结点的入度
        vector<vector<int>> edge;//记录边的状态
        init();
        for(int i = 0; i < n; i ++){
            cin >> s >> t;
            inDegree[t] ++;
            edge.push_back({s, t});
        }
        vector<int> vec;//记录入度为2的边的编号
        for(int i = n - 1; i >= 0; i --){ //注意这里是倒序！！
            if(inDegree[edge[i][1]] == 2){
                vec.push_back(i);
            }
        }
        
        if(vec.size() > 0){//vec只要不为0,那么必然存在2条边可选
            if(isTreeAfterRemove(edge, vec[0])){//这里尝试删除标准输入里面的相对位置最后的边
                cout << edge[vec[0]][0] << " " << edge[vec[0]][1] << endl;
                return 0;
            }else{//上面代码没有解决问题，那么说明需要删除下面这条边
                cout << edge[vec[1]][0] << " " << edge[vec[1]][1] << endl;
                return 0;
            }
        }
        getRemove(edge);//这里是在上述vec大小为0,也就是说不存在入度为2的结点，那么此时必然存在成环的边，找到并删除
    }
}

感谢你的阅读，希望我的文章能够给你帮助，如果有帮助，麻烦点赞加收藏，或者点点关注，非常感谢。

如果有什么问题欢迎评论区讨论！