解题思路

【并查集判断图中是否存在环】合并之前如果两个点已经在一个集合里，那么合并之后就必然会形成环。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从点 $x$ 到点 $y$ 的无向边 ($x$,$y$)。

输入

3 3
1 2
2 3
1 3

输出

有环！

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int p[N], n, m;

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) p[i] = i;

    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        a = find(a), b = find(b);
        if (a != b) p[a] = b;
        else 
        {
            puts("有环！");
            return 0;
        }
    }

    puts("无环！");
    return 0;    
}

以上这种方式仅适用于无向图，下面的方法有向图和无向图都适用。不过 求拓扑序列一般都针对的是有向图，因为拓扑序列考虑先后次序。

基于DFS的拓扑排序（求逆拓扑序列）

深度优先遍历判断图中拓扑排序（是否无环）的算法如下:

1. 选择一个起始节点,将其标记为”正在访问”状态。

2. 检查当前节点的所有相邻节点:

   • 如果相邻节点为”未访问”状态,则递归地进行深度优先搜索这个节点

3. 如果在搜索过程中发现这个节点已经被标记为”正在访问”,则说明存在环路,返回false

4. 如果相邻节点状态为”已访问”,忽略该节点

5. 所有相邻节点均处理完成后,将当前节点标记为”已访问”状态,并返回上层递归

6. 如果整个图都搜索完,没有返回false,则说明图中不存在环路,返回true。

主要思路是:

• 使用”未访问”、”正在访问”和”已访问”三种节点状态进行标记

• 如果搜索某个节点时发现其状态为”正在访问”,则说明从此节点开始一定存在一个环路

• 整个深度优先搜索结束没有返回false,则该图不存在环路

通过遍历每个节点及其相邻节点,并检查其访问状态就可以判断是否存在环路。时间复杂度为O(V+E),空间复杂度为O(V)。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m, q[N], top;
int st[N];  // 0表示没有遍历过，1表示在递归当中，2表示已经遍历完了

struct Node
{
    int id;
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];      // 头插法
    head[a] = p;
}

bool dfs(int u)     // 如果有环的话返回false
{
    st[u] = 1;      // 标记当前点在递归中

    for (Node* p = head[u]; p; p = p->next)
    {
        int j = p->id;
        if (!st[j])     // 如果没有搜过的话（0）就直接搜
        {
            if (!dfs(j)) return false;  // 如果搜的过程中出现了环，直接false
        }
        else if (st[j] == 1) return false;   // 否则如果发现这个点在递归当中，直接false
    }

    q[top ++] = u;

    st[u] = 2;      // 标记当前点已经遍历完了

    return true;
}

// 基于深搜的话要遍历所有点，因为这个图不一定是联通的
bool topsort()
{
    for (int i = 1; i <= n; i ++)
        if (!st[i] && !dfs(i)) // 如果没遍历的话就遍历它，如果发现有环的话直接false
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    if (topsort())
    {
        // 因为得到的是拓扑排序的逆序序列，所以要倒序输出
        for (int i = n - 1; i >= 0; i -- ) cout << q[i] << ' ';
        cout << endl;
    }
    else puts("-1");

    return 0;
}