并查集能不能找到有向图的环

Question

使用并查集来判断一个图中是否存在环：

对于无向图来说，在遍历边（u-v）时，如果结点 u 和结点 v 的“父亲”相同，那么结点 u 和结点 v 在同一个环中。

对于有向图来说，在遍历边（u->v）时，如果结点 u 的“父亲”是结点 v，那么结点 u 和结点 v 在同一个环中。

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

vector<pair<int, int>> g;
vector<int> father;

int findFather(int x) {
    int a = x;
    while (x != father[x]) {
        x = father[x];
    }
    while (a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}

void Union(int a, int b) {
    int fa = findFather(a);
    int fb = findFather(b);
    father[a] = father[b] = min(fa, fb);
}

bool isCyclicUnirectedGraph() {
    for (int i = 0; i < g.size(); i++) {
        int u = g[i].first;
        int v = g[i].second;
        if (father[u] == father[v]) {
            return true;
        }
        Union(u, v);
    }
    return false;
}

bool isCyclicDirectedGraph() {
    for (int i = 0; i < g.size(); i++) {
        int u = g[i].first;
        int v = g[i].second;
        if (father[u] == v) {
            return true;
        }
        father[v] = findFather(u);
    }
    return false;
}

int main() {
    // Undirected acyclic graph
    //   0
    //  / \
    // 1   2
    g.push_back(make_pair(0, 1));
    g.push_back(make_pair(0, 2));
    for (int i = 0; i < 3; i++) {
        father.push_back(i);
    }
    cout << isCyclicUnirectedGraph() << endl;   //0，无环
    // Undirected cyclic graph
    //   0
    //  / \
    // 1———2
    g.push_back(make_pair(1, 2));
    vector<int>().swap(father);
    for (int i = 0; i < 3; i++) {
        father.push_back(i);
    }
    cout << isCyclicUnirectedGraph() << endl;   //1，有环
    // Directed acyclic graph
    //   0
    //  / \
    // v   v
    // 1——>2
    vector<pair<int, int>>().swap(g);
    g.push_back(make_pair(0, 1));
    g.push_back(make_pair(1, 2));
    g.push_back(make_pair(0, 2));
    vector<int>().swap(father);
    for (int i = 0; i < 3; i++) {
        father.push_back(i);
    }
    cout << isCyclicDirectedGraph() << endl;    //0，无环
    // Directed cyclic graph
    //   0
    //  / ^
    // v   \
    // 1——>2
    g.pop_back();
    g.push_back(make_pair(2, 0));
    vector<int>().swap(father);
    for (int i = 0; i < 3; i++) {
        father.push_back(i);
    }
    cout << isCyclicDirectedGraph() << endl;    //1，有环
    return 0;
}

Answer 1

liuyubobobo 2021-12-07 14:01:23

没有看具体逻辑，但稍微测试了一下，对于这个用例是错误的：

0->1

1->2

2->3

3->1

这个图有环，你的算法会返回 0。

继续加油！：）

• 提问者 慕用0058068 #1

  就是并查集只能检测无向图的环，有向图其实不能，哈哈，对吧～

• liuyubobobo 回复 提问者 慕用0058068 #2

  我不能 100% 肯定，但我确实没有见过用 uf 做有向图的环检测：）