拓扑排序

给定一个有向无环图(DAG)，排出所有顶点的一个序列A满足：对于图中每条有向边(x,y),x在A中都出现在y之前，则A是该图中的顶点的一个拓扑序

拓扑排序可以判断有向图中是否有环，可以生成拓扑序列

Kahn（卡恩）算法

e[x]存点x的邻点，res存拓扑序列，d[x]存x的入度

算法流程：核心用队列维护一个入度为0的节点的集合。

初始化，队列q压入所有入度为0的点；
每次从q中取出一个点x放入数组res;
然后将×的所有出边删除。若将边(x,y)删除后，y的入度变为0，则将y压入q中
不断重复2,3过程，直到队列q为空。
res中的元素个数等于n,则有拓扑序；否则，有环。

题目-有向图的拓扑序列

链接：https://www.acwing.com/problem/content/850/

给定一个 $n$ 个点 $m$ 条边的有向图，点的编号是 $1$ 到 $n$ ，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 $-1$ 。

若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x, y)$ ， $x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的一个拓扑序列。

输入格式

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

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

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 $-1$ 。

数据范围

$1 \le n,m \le 10^5$

输入样例：

输出样例：

1 2 3

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m;
vector<int> e[N], res;
vector<int> d(N);

bool topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) q.push(i);
    }
    while (q.size()) {
        auto t = q.front();
        q.pop();
        res.push_back(t);
        for (auto y: e[t]) {
            if (--d[y] == 0) q.push(y);
        }
    }
    return res.size() == n;
}


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        d[y]++;
    }
    if (topsort()) {
        for (const auto &item: res) {
            cout << item << " ";
        }
    } else {
        cout << -1 << endl;
    }
    return 0;
}

DFS算法

e[x]存点x的邻点，res存拓扑序列，d[x]存x的入度

算法的核心是变色法，一路搜一路给点变色，如果有拓扑序，每个点的颜色都会从0→-1→1，经历三次变色。

初始状态，所有点染色为0。
枚举每个点，进入×点，把x染色为-1。然后，枚举x的儿子y,如果y的颜色为0，说明没碰过该点，进入y继续走，
如果枚举完×的儿子，没发现环，则×染色为1，并把×压入tp数组
如果发现有个熊孩子的颜色为-1，说明回到了祖先节点，发现了环，则一路返回false,退出程序

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1e5 + 10;
vector<int> e[N], res, c(N);
int n, m;

int dfs(int x) {
    c[x] = -1;
    for (auto y: e[x]) {
        if (c[y] == -1) return 0;//有环
        else if (c[y] == 0) {
            int t = dfs(y);
            if (t == 0) return 0;
        }
    }
    c[x] = 1;
    res.push_back(x);
    return 1;
}

bool topsort() {
    for (int i = 1; i <= n; i++) {
        if (c[i] == 0) {
            int t = dfs(i);
            if (t == 0) return 0;
        }
    }
    std::reverse(res.begin(), res.end());
    return 1;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
    }
    if (topsort()) {
        for (const auto &item: res) {
            cout << item << " ";
        }
    } else {
        cout << -1 << endl;
    }


    return 0;
}

拓扑排序

拓扑序列：是对于有向图而言的，有向图的拓扑序是其顶点的线性排序，使得对于从顶点u到顶点v的每个有向边uv在序列中都在v之前。步骤:

首先记录各个点的入度
然后将入度为 0 的点放入队列
将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同时边的另一侧的点的入度 -1。
如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++tt] = i;
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }
    return tt == n - 1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }
    if (!topsort()) couf << "-1";
    else {
        for (int i = 0; i < n; ++i) cout << q[i] << " ";
    }
    return 0;
}

AcWing 1191. 家谱树

题目

https://www.acwing.com/problem/content/1193/ 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。输出一个序列，使得每个人的孩子都比那个人后列出。

思路

显然，模板题

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = N * N / 2;
int n;
int h[N], e[M], ne[M], idx;
int q[N], d[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


void topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++tt] = i;

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q[++tt] = j;
        }
    }

}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i++) {
        int son;
        while (cin >> son, son) {
            add(i, son);
            d[son]++;
        }
    }
    topsort();
    for (int i = 0; i < n; i++) cout << q[i] << " ";
    return 0;
}

AcWing 1192. 奖金

题目

https://www.acwing.com/problem/content/1194/ 公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开 m 方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工 a 的奖金应该比 b 高！” Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元，且必须是整数。

思路

简化版的差分约束判断是否存在拓扑排序，因为要求最小值，所有求一遍最长路

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 20010;
int n, m;
int h[N], e[M], ne[M], idx;
int q[N], d[N];
int dist[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort() {
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(!d[i])
            q[++tt]=i;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0) q[++tt]=j;
        }
    }
    return tt==n-1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(b, a);
        d[a]++;
    }
    if (!topsort()) cout << "Poor Xed";
    else {
        for (int i = 1; i <= n; i++) dist[i] = 100;
        for (int i = 0; i < n; i++) {
            int j = q[i];
            for (int k = h[j]; ~k; k = ne[k])
                dist[e[k]] = max(dist[e[k]], dist[j] + 1);
        }
        int res = 0;
        for (int i = 1; i <= n; i++) res += dist[i];
        cout << res;
    }
    return 0;
}

Kahn（卡恩）算法​

题目-有向图的拓扑序列​

输入格式​

输出格式​

数据范围​

输入样例：​

输出样例：​

代码​

DFS算法​

代码​

拓扑排序​

AcWing 1191. 家谱树​

题目​

思路​

代码​

AcWing 1192. 奖金​

题目​

思路​

代码​

Kahn（卡恩）算法

题目-有向图的拓扑序列

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

DFS算法

代码

拓扑排序

AcWing 1191. 家谱树

题目

思路

代码

AcWing 1192. 奖金

题目

思路

代码