Algorithm14.3 拓扑图

[TOC]

拓扑图

https://www.luogu.com.cn/problem/P4017

1、图存储的数据结构:邻接矩阵,mp[a][b],等于1的时候表示的是

2、根据入度、出度来看是否添加进入队列。

#include <iostream>
using namespace std;
#define maxn 5005
int n, m, mp[maxn][maxn], in[maxn], out[maxn], ta, tb, ans[maxn], final;
#include <queue>
queue<int> q;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        mp[ta][tb] = 1;
        out[ta]++;in[tb]++;
    }
    for (int i = 1; i <= n; ++i) if (!in[i]) {ans[i] = 1;q.push(i);}
    while (!q.empty()) {
        int nw = q.front();q.pop();
        for (int i = 1; i <= n; ++i){
            if (mp[nw][i]) {
                ans[i] += ans[nw];ans[i] %= 80112002;
                in[i]--;
                if (!in[i]) {
                    if (!out[i]) {
                        final += ans[i];final %= 80112002;
                        continue;
                    }
                    q.push(i);
                }
            }
        }
    }
    printf("%d\n", final);
    return 0;
}
Posted on Feb 1, 2021