代码随想录算法训练day62---图论系列6《并查集2》

代码随想录算法训练

—day62

前言

今天是算法营的第62天，希望自己能够坚持下来！
今天继续并查集系列！今日任务：
● 108.冗余连接
● 109.冗余连接II

一、108.冗余连接

卡码网题目链接
文章讲解

思路：
无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树。
如果有多个答案，则返回二维数组中最后出现的边。
那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合。
如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

代码如下：

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

int n;
vector<int> father = vector<int>(1001, 0);

void init() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

int find(int u) {
    return u == father[u]? u : father[u] = find(father[u]);
}

bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    
    return u == v;
}

void join(int u, int v) {
    u = find(u);
    v = find(v);
    
    if (u == v) return;
    father[v] = u;
}

//遍历每一条边，把每一条边加入集合，当s,t同根的时候，说明发生了闭环，此时的s,t就是要去掉边
int main() {
    int s, t;
    cin >> n;
    init();
    
    for (int i = 1; i <= n; i++) {
        cin >> s >> t;
        if (isSame(s, t)) {
            cout << s << " " << t << endl;
            return 0;
        } else {
            join(s, t);
        }
        
    }
}

二、109. 冗余连接II

卡码网题目链接
文章讲解

思路：
与 108.冗余连接 类似，但本题是一个有向图，有向图相对要复杂一些。

如果是有向树的话，只有根节点入度为0，其他节点入度都为1
所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。

但 入度为2 还有一种情况，情况二，只能删特定的一条边，如图：
综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

情况三： 如果没有入度为2的点，说明 图中有环了（注意是有向环）。

对于情况三，删掉构成环的边就可以了。

#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father = vector<int>(1001, 0);
 
void init() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}
 
int find(int u) {
    return u == father[u]? u : father[u] = find(father[u]);
}
 
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
 
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    father[v] = u;
}
 
void getRemoveEdge(const vector<vector<int>>& edges) {
    init();
    for (int i = 0; i < n; i++) {
        if (isSame(edges[i][0], edges[i][1])) { //构成环了，这条就是要删的边
            cout << edges[i][0] << " " << edges[i][1] << endl;
        } else {
            join(edges[i][0], edges[i][1]);
        }
    }
}
 
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
    init();
    for (int i = 0; i < n; i++) {
        if (i == deleteEdge) continue; //要删掉的边不添加到集合中
        if (isSame(edges[i][0], edges[i][1])) { //构成环了，说明不是树
            return false;
        }
        join(edges[i][0], edges[i][1]);
    }
    return true;
}
 
int main() {
    int s, t;
    vector<vector<int>> edges; //用来存放每条边
    cin >> n;
     
    vector<int> inDegree(n + 1, 0); //记录节点入度
    for (int i = 0 ;i < n; i++) {
        cin >> s >> t; //s->t
        inDegree[t]++; //t的入度+1
        edges.push_back({s,t}); //存放每条边
    }
     
    vector<int> vec; //存放入度为2的边
    //遍历每行，判断指向的节点是否入度为2，后序遍历，因为要优先删除最后出现的边
    for (int i = n - 1; i >= 0; i--) {
        if (inDegree[edges[i][1]] == 2) vec.push_back(i);
    }
     
    //情况一、情况二
    if (vec.size() > 0) {
        //放在vec里的边已经按照倒叙放了，所以这里优先删除vec[0]这条边
        if (isTreeAfterRemoveEdge(edges, vec[0])) {
            //如果删除这条边之后，是树，则这条边是答案，vec[0]是边的下标
            cout << edges[vec[0]][0] << " " << edges[vec[0]][1] << endl;
        } else {
            cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;
        }
        return 0;
    }
     
    //情况三，没有入度为2的节点，说明有环,找到构成环的边返回就可以了
    getRemoveEdge(edges);
    return 0;
}

总结

• 是否有环：遍历每一条边，将边加入到集合中，如果当前遍历的边是同根isSame（u,v）=true，说明已经在集合里了，行成了环
• 有向树的话，只有根节点入度为0，其他节点入度都为1

明天继续加油！