对于拓扑排序有向图方向的迷惑

戴嘚嘚嘚嘚嘚 @ 2022-03-28 02:33:10

by Qiaoqia @ 2022-03-28 06:53:59

@戴嘚嘚嘚嘚嘚

题目中说“等级大于等于火车站 x 的站都必须停靠”，即等级高的是要先于等级低的，而拓扑排序中，若存在边 u \to v 则 u 一定排在 v 前，所以应该是等级高的指向等级低的，因为等级高的要排在前面。

by 戴嘚嘚嘚嘚嘚 @ 2022-03-28 13:30:20

@Qiaoqia 太感谢了！终于明白了！

by Centre @ 2022-08-25 00:26:00

我也是等级低指向等级高啊，过了 个人感觉画完图以后，接下来do-while就是在图中找一个深度最大的树，无论高级指向低级或者低级指向高级，也不管存的是出度还是入度，都可以。

下附AC代码

#include <iostream>
#include <cstring>
#define N 1010
#define rr read()
using namespace std;
inline int read(){
    register int x = 0, f = 1;
    register char ch = getchar();
    while(ch<'0' || ch>'9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int n, m;
int s, st[N];
bool vis[N];
int topo[N][N], deg[N];
int top, S[N];
bool del[N];
int ans;

void Delete(int tar){
    for(int i=1; i<=n; i++)
        if(topo[i][tar]){
            topo[i][tar] = 0;
            deg[i]--;
        }
}

int main()
{
    n = rr; m = rr;
    for(int i=1; i<=m; i++){
        memset(vis, 0, sizeof(vis));
        s = rr;
        for(int j=1; j<=s; j++){
            st[j] = rr;
            vis[st[j]] = 1;
        }
        for(int j=st[1]; j<=st[s]; j++)
            if(!vis[j])
                for(int k=1; k<=s; k++)
                    if(topo[st[k]][j] == 0){
                        topo[st[k]][j] = 1; // j指向st[]
                        deg[st[k]]++;
                    }
    }

    do{
        top = 0;
        for(int i=1; i<=n; i++){
            if(!deg[i] && !del[i]){
                S[++top] = i;
                del[i] = 1;
            }
        }
        for(int i=1; i<=top; i++)
            Delete(S[i]);
        ans++;
    }while(top);
    ans--;

    printf("%d", ans);
    return 0;
}