图论PLUS

拓扑排序

Kahn（卡恩）算法

$e[x]$ 存点 $x$ 的邻点，$tp$ 存拓扑序列， $din[x]$ 存点 $x$ 的入度。算法的核心用队列维护一个入度为 $0$ 的节点的集合

  1. 初始化，队列 $q$ 压入所有入度为 $0$ 的点；
  2. 每次从 $q$ 中取出一个点 $×$ 放入数组 $tp$;
  3. 然后将 $x$ 的所有出边删除。若将边 $(x,y)$ 删除后，$y$ 的入度变为 $0$，则将 $y$ 压入 $q$ 中;
  4. 不断重复 $2,3$ 过程，直到队列 $q$ 为空；
  5. 若 $tp$ 中的元素个数等于 $n$ ，则有拓扑序；否则，有环。
image-20230724203328976 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 100010;
vector<int> e[N]; // e[x] 存点x的邻点
vector<int> tp;   // 拓扑序列
int din[N];       // din[x]存点x的入度

bool toposort() // 拓扑排序 卡恩算法
{
    queue<int> q; // 临时队列
    for (int i = 1; i <= n; i++)
        if (din[i] == 0) // 入度为0，入q
            q.push(i);
    while (q.size()) // 队列不为空
    {
        int x = q.front();
        q.pop();            // 出队
        tp.push_back(x);    // 进拓扑序列
        for (auto y : e[x]) // 遍历边
        {
            if (--din[y] == 0) // 入度减一，判断入度是否为0，进行插入
                q.push(y);
        }
    }
    return tp.size() == n; // 根据拓扑序列的大小，判断是否有环
}

找到字典序最小的拓扑排序，将队列换为优先队列（小根堆）。

DFS算法

$e[x]$ 存点 $x$ 的邻点， $tp$ 存拓扑序列， $c[x]$ 存点 $x$ 的颜色。
算法的核心是变色法，一路搜一路给点变色，如果有拓扑序，每个点的颜色都会从 $0→-1→1$ ，经历三次变色。

  1. 初始状态，所有点染色为 $0$ ；
  2. 枚举每个点，进入 $x$ 点，把 $x$ 染色为 $-1$ 。然后，枚举 $x$ 的儿子 $y$ ，如果 $y$ 的颜色为 $0$ ， 说明没碰过该点，进入 $y$ 继续走；
  3. 如果枚举完 $x$ 的儿子，没发现环，则 $x$ 染色为 $1$ ，并把 $x$ 压入 $tp$ 数组；
  4. 如果发现有个熊孩子的颜色为 $-1$ ，说明回到了祖先节点，发现了环，则一路返回 false ，退出程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const int N = 100010;
int n;            // 顶点数
vector<int> e[N]; // e[x]=y，代表x->y的一条边
vector<int> tp;   // 拓扑序列
int c[N];         // 染色数组 进入染色为-1，初始为0，已入序列为1
bool dfs(int x)
{
    c[x] = -1;         // 进入染色为-1
    for (int y : e[x]) // 遍历儿子
    {
        if (c[y] < 0)     // 找到-1，代表访问到了父节点，成环
            return 0;     // 有环
        else if (!c[y])   // 未染色
            if (!dfs(y))  // 深搜内发现了父节点
                return 0; // 有环
    }
    c[x] = 1;        // 已入序列，染色为1
    tp.push_back(x); // 插入拓扑序列
    return 1;        // 返回成功
}