求助，加虚拟点拓扑排序的方法思路是怎么样的

Compound_Interest @ 2022-03-14 16:51:52

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2e3+10;
int a[maxn],n,m,b[maxn],cnt,in[maxn],num,G[maxn][maxn],ans;
bool book[maxn],vis[maxn];
int main(){
    scanf("%d%d",&n,&m);
    int tmp;
    for(int i=1;i<=m;i++){
        memset(book,0,sizeof(book));
        scanf("%d",&tmp);
        for(int j=1;j<=tmp;j++){
            scanf("%d",&a[j]);book[a[j]]=1;
        }
        for(int j=a[1];j<=a[tmp];j++)
            if(!book[j]){
                G[j][n+i]=1,in[n+i]++;
        //      printf("%d->%d\n",j,n+i);
            }
        for(int j=1;j<=tmp;j++){
            G[n+i][a[j]]=1,in[a[j]]++;
        //  printf("%d->%d\n",n+i,a[j]);
        }
    }
/*  for(int i=1;i<=n+m;i++)
        for(int j=1;j<=n+m;j++)
            if(G[i][j]) printf("%d->%d\n",i,j);*/
    while(1){
        bool flag=1;
        cnt=0;
        for(int i=1;i<=n+m;i++) if(!in[i]&&!vis[i]){
            b[++cnt]=i,vis[i]=1;
            if(i>n) flag=0;
        }
        //for(int i=1;i<=cnt;i++) printf("b[%d]=%d\n",i,b[i]);1
        if(!cnt) break;
        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=n+m;j++)
                if(G[b[i]][j]&&!vis[j]){
                    in[j]--;
                //  printf("in[%d]=%d\n",j,in[j]);
                }       
        ans+=flag;
    }
    printf("%d",ans);
    return 0;
}

by piggy123 @ 2022-03-16 10:07:25

@x17875487211 你的感觉是正确的，我也在这个地方错了inf次。我的解决办法是先出队虚点，再出队实点，这样保证在队内的都是实点：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll vis[3005],in[3005];
vector<ll> to[3005];

int main() {
    ll n,m;
    cin >> n >> m;
    for (ll i=1; i<=m; i++) {
        ll s;
        cin >> s;
        ll st,ed;
        cin >> st;
        memset(vis,0,sizeof(vis));
        for (ll j=2; j<s; j++) {
            ll x;
            cin >> x;
            vis[x]=1;
        }
        cin >> ed;
        vis[st]=1,vis[ed]=1;
        for (ll j=st; j<=ed; j++) {
            if (vis[j]) {
                in[j]++;
                to[i+n].push_back(j);
            }
        }
        for (ll j=st; j<=ed; j++) {
            if (!vis[j]) {
                in[i+n]++;
                to[j].push_back(i+n);
            }
        }
    }
    ll cnt=0;
    queue<ll> q;
    for (ll i=1; i<=m; i++) {
        if (in[i+n]==0) {
            in[i+n]--;
            for (ll j:to[i+n]) {
                in[j]--;
            }
        }
    }
    for (ll i=1; i<=n; i++) {
        if (in[i]==0)q.push(i),in[i]--;
    }
    while (!q.empty()) {
        while (!q.empty()) {
            ll tp=q.front();
//          cout << tp << endl;
            q.pop();
            for (ll i:to[tp]) {
                in[i]--;
            }
        }
        cnt++;
        for (ll i=1; i<=m; i++) {
            if (in[i+n]==0) {
                in[i+n]--;
                for (ll j:to[i+n]) {
                    in[j]--;
                }
            }
        }
        for (ll i=1; i<=n; i++) {
            if (in[i]==0) {
                q.push(i),in[i]--;
            }
        }

    }
    cout << cnt;
    return 0;
}

by Compound_Interest @ 2022-03-16 13:27:10

请问有没有具体的例子，什么情况虚点和实点在同一层