【1146】Topological Order (25分)【拓扑排序】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//如果当前的结点入度≠0则不是拓扑序列，如果为0则将它能到达的结点的入度-1
//一定要注意多个for循环的循环变量i不能写混乱，可以为i、ii、iii
int main(){   
  int n,m;//点数n  边数m
  vector<int> v[1010];
  scanf("%d %d",&n,&m);
  int in[1000+1]={0};
  int a,b;
  //用邻接表保存这个图
  for(int i=0;i<m;i++){
    scanf("%d %d",&a,&b);
    v[a].push_back(b);//a指向b结点
    in[b]++;//b结点的入度＋1
  }
  int k;
  scanf("%d",&k);//k次查询
  bool space=false;//是否输出空格
  for(int i=0;i<k;i++){
    int A[1010];
    for(int ii=0;ii<n;ii++)
      scanf("%d",&A[ii]);//读入一次查询的拓扑序列
    vector<int>temp(in,in+n+1);
    for(int iii=0;iii<n;iii++)
      if(temp[A[iii]]!=0){//当前入度不为0,则非拓扑序列
        printf("%s%d",space?" ":"",i);
        space=true;
        break;
      }else{//入度为0
        for(int j:v[A[iii]])//遍历能到达的结点并将入度-1
          --temp[j];
      }
  }
  system("pause");
    return 0;   
}