B1146 Topological Order (拓扑排序)

B1146 Topological Order (25分)

不用完全模拟拓扑排序，备份入度记录数组，对序列的每个数字判断入度是否为0，若不是0则判断该序列不是拓扑序列，若是0，对该数字出边所能到达的数字的入度减减，重复以上操作。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=10010;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=633;
int n,m,k;
vector<int>G[MAX];
vector<int>vt;
vector<int>res;
bool topologicalsort(int temp[])
{
   int flag=1;
   queue<int>q;
   for(int i=0;i<vt.size();i++)
   {
       if(temp[vt[i]]==0)
       {
           for(int j=0;j<G[vt[i]].size();j++)
           {
               temp[G[vt[i]][j]]--;
           }
       }
       else
        flag=0;
   }
   if(flag==0)
    return false;
   else
    return true;
}
int main()
{
    int indegree[MAX];
    int ans[MAX];
    memset(indegree,0,sizeof(indegree));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        indegree[y]++;
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        vt.clear();
        for(int i=0;i<n;i++)
        {
            int t;
            scanf("%d",&t);
            vt.push_back(t);
        }
        for(int i=1;i<=n;i++)
            ans[i]=indegree[i];
        if(!topologicalsort(ans))
            res.push_back(i);
    }
    for(int i=0;i<res.size();i++)
    {
        if(i==0)
            printf("%d",res[i]);
        else
            printf(" %d",res[i]);
    }
    return 0;
}