关于算法-数据结构:PAT甲级1146-Topological-Order

题目粗心：

给定一个有向图，N 个顶点，M 条边，现给定 K 个查问，每一个查问输出一个序列，判断该序列是否是该图的拓扑排序序列，如果不是，输入该序列的编号 (从 0 开始)

算法思路：

模仿拓扑排序的过程，对于输出的序列，先查看其入度是否为 0，不为 0 阐明该序列不是拓扑排序序列，否则就将该结点的邻接点的入度全副减一，顺次向下进行判断，晓得退出循环。为了避免最初一个测试点的格局谬误，所有不是拓扑排序的序列编号都应用 result 数组保留，最初输入后果即可。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>

using namespace std;

const int maxn = 1005; 
int inDegree[maxn];// 每一个结点的入度 
int tempInDegree[maxn];// 每次查问暂存入度数组 
int query[maxn];// 每次查问的序列 
vector<int> Adj[maxn];// 邻接表，保留每一个结点的所有邻接点 
vector<int> result;// 保留所有不是拓扑排序序列的编号 
int N,M;

bool isTopologicalOrder(){for(int i=1;i<=N;++i){
        // 从新赋值入度数组 
        tempInDegree[i] = inDegree[i];
    }
    for(int i=0;i<N;++i){if(tempInDegree[query[i]]!=0){return false;}
        for(auto &item:Adj[query[i]]){
            // 将以后顶点的邻接点的入度减一
            --tempInDegree[item];
        }
    }
    return true;
}

int main(){scanf("%d %d",&N,&M);
    for(int i=0;i<M;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        ++inDegree[b];
        Adj[a].push_back(b);
    }
    int K;
    scanf("%d",&K);
    for(int i=0;i<K;++i){for(int j=0;j<N;++j){scanf("%d",&query[j]);
        }
        if(!isTopologicalOrder()){result.push_back(i);
        }
    }
    for(int i=0;i<result.size();++i){printf("%d",result[i]);
        if(i<result.size()-1) printf(" ");
    }
    return 0;
}