拓扑排序

拓扑序 = DAG 的线性化：把「u 在 v 前」的偏序展平成一条链。
所以只有 DAG 才有拓扑序。队列弹出数 < n ⇒ 有环 —— 判环万能判据。

1
2
3
4
5
6
7
8
// Kahn 模板骨架
queue<int> q; for (i) if (!ind[i]) q.push(i);
int cnt = 0;
while (!q.empty()) {
    int u = q.front(); q.pop(); cnt++;
    for (v : e[u]) if (--ind[v] == 0) q.push(v);
}
// cnt < n , 有环

P1347 排序

P1347 [ECNA 2001] 排序 - 洛谷

这道题就是边排序边判断，其他都可以套模板。每读入一条关系就重跑一遍拓扑，返回三种状态：

  • -1：弹出点数 cnt < n，说明有环，矛盾；
  • 1：cnt == n 且队列任何时刻都只有一个元素（sure 没被置 false），说明拓扑序唯一，可以确定；
  • 0：能排完但不唯一，信息不足，继续加关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;

vector<int> g[30];
int indeg[30];
int n,m;

int sort(int& orderCount,string& orderStr){
    int tmpIndeg[30];
    for(int i=0;i<n;i++) tmpIndeg[i]=indeg[i];

    queue<int> q;
    for(int i=0;i<n;i++){
        if(tmpIndeg[i]==0) q.push(i);
    }

    int cnt=0;
    bool sure=true;
    string res="";

    while(!q.empty()){
        if(q.size()>1) sure=false;
        int u=q.front(); q.pop();
        res.push_back(char('A'+u));
        cnt++;

        for(int v:g[u]){
            tmpIndeg[v]--;
            if(tmpIndeg[v]==0) q.push(v);
        }
    }

    orderCount=cnt; orderStr=res;
    if(cnt<n) return -1;
    if(sure && cnt==n) return 1;
    return 0;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;

    for(int i=0;i<m;i++){
        string s; cin>>s;
        int u=s[0]-'A';
        int v=s[2]-'A';
        g[u].push_back(v);
        indeg[v]++;

        int cnt;
        string order;
        int status=sort(cnt,order);
        if(status==1){
            cout << "Sorted sequence determined after " << i + 1 << " relations: " << order << "." << endl;
            return 0;
        }else if(status==-1){
            cout << "Inconsistency found after " << i + 1 << " relations." << endl;
            return 0;
        }
    }

    cout<<"Sorted sequence cannot be determined." << endl;
    return 0;
}

P1137 旅行计划

P1137 旅行计划 - 洛谷

这道题参杂了一点点 dp，因为最大城市数取决于之前的情况，走过的岔路口肯定要判断一下怎么走最优。

把入度为 0 的点（起点）dp 初始化成 1，然后在 Kahn 的松弛过程中转移：dp[v] = max(dp[v], dp[u] + 1)。因为队列弹出的顺序天然是拓扑序，转移到 v 时它的所有前驱都已经算完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll=long long;
const int maxn=200005;

vector<int> g[maxn];
int indeg[maxn];
int dp[maxn];
int n,m;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y; cin>>x>>y;
        g[x].push_back(y);
        indeg[y]++;
    }

    queue<int> q;
    for(int i=1;i<=n;i++){
        if(indeg[i]==0){
            q.push(i);
            dp[i]=1;
        }
    }

    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            dp[v]=max(dp[v],dp[u]+1);
            indeg[v]--;

            if(indeg[v]==0) q.push(v);
        }
    }

    for(int i=1;i<=n;i++){
        cout<<dp[i]<<endl;
    }

    return 0;
}

P4017 最大食物链计数

P4017 最大食物链计数 - 洛谷

也就是求一共有几条生物链，最大的意思就是从生产者到最顶端的消费者，路径 dp 取模。

和上一题是同一个骨架，区别在于转移从取 max 变成累加计数：

  • 起点（入度 0，即生产者）dp[i] = 1；
  • 转移 dp[v] = (dp[v] + dp[u]) % mod；
  • 答案不再是所有点求和，而是只累加出度为 0 的点（g[i].empty()，即食物链顶端）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

const int mod=80112002;
const int maxn=500005;

vector<int> g[maxn];
int indeg[maxn];
ll dp[maxn];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m; cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        indeg[b]++;
    }

    queue<int> q;
    for(int i=1;i<=n;i++){
        if(indeg[i]==0){
            q.push(i);
            dp[i]=1;
        }
    }

    while(!q.empty()){
        int u=q.front(); q.pop();

        for(int v:g[u]){
            dp[v]=(dp[v]+dp[u])%mod; //算路径
            indeg[v]--;
            if(indeg[v]==0) q.push(v);
        }
    }

    ll ans=0;
    for(int i=1;i<=n;i++){
        if(g[i].empty()){  //g[i]出度为零，证明是食物链顶端
            ans=(ans+dp[i])%mod;
        }
    }

    cout<<ans<<endl;
    return 0;
}