PAT甲级1146.

目录

A1146

题目

样例

输入:

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
6
5 2 3 6 4 1
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

输出:

0 4 5

思路和坑点

　　思路:
　　按照拓扑排序的思路执行每一个串判别的序列，如果中间出现某个顶点的入度不为0，则说明此序列不是拓扑排序的序列。

AC代码

#include<bits/stdc++.h>
using namespace std;
int indegree[1003]={0};                 //记录每一个结点的入度
vector<int> G[1003];                    //二维数组记录图
int n,m;    
int cnt=0;                              //计数器控制输出格式
void Judge(int q); 
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int a,b,k;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b);              //邻接表表示图
        indegree[b]++;                  //b的入度增加
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)                //判断k个序列是不是拓扑排序
        Judge(i);
    return 0;    
}
void Judge(int q)
{
    int flag=true;                      //判断标记
    vector<int> ind(n+1);               //初始化临时的入度数组
    for(int i=1;i<=n;i++)
        ind[i]=indegree[i];
    for(int i=0;i<n;i++){               //读入序列
        int temp;
        scanf("%d",&temp);
        if(ind[temp]!=0){               //如果按照拓扑排序的方式处理发现某一个顶点的入度不为0则不能构成拓扑排序
            flag=false;
            while(getchar()!='\n')      //后序序列不用再判定了，直接吸收过滤后边多余字符
                continue;
            break;
        }
        else                            //否则把当前结点后继的所有顶点的度减一，继续循环
            for(int j=0;j<G[temp].size();j++)
                ind[G[temp][j]]--;
    } 
    if(flag==false){                    //根据标记判断是否输出
        if(cnt++) putchar(' ');
        printf("%d",q);
    }
}