爆刷PAT（甲级）——之【1146】 Topological Order（25 分）——拓扑排序

最新推荐文章于 2024-06-16 23:23:07 发布

仰天倀笑

最新推荐文章于 2024-06-16 23:23:07 发布

阅读量406

点赞数

分类专栏： # PAT甲级【爆刷】文章标签：爆刷PAT甲级算法学习训练基础算法编程 1146 Topological Order（25 分）拓扑排序

本文链接：https://blog.csdn.net/Hide_in_Code/article/details/82153417

版权

PAT甲级【爆刷】专栏收录该内容

35 篇文章

订阅专栏

博客围绕PAT甲级题目，判断网络拓扑中给定序列是否为拓扑排序序列。指出序列编号从0开始这一难点，介绍算法思路，即保存各点入度，遍历序列，若当前节点入度非0则非拓扑序列，还说明了统计入度的方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

艰难的英语单词：topological 英 [tɒpə'lɒdʒɪkəl 拓扑（学）的 adj.

题意：给一个网络拓扑，给出Q个序列，问哪些不是拓扑排序序列。如果不是，就输出这个序列的编号。

难点：序列的编号是从0开始的，也就是说样例的3、4表示的意思是第四个和第五个序列不是拓扑排序序列。

算法思路即：保存每个点的入度，然后对于每个序列，都扫一遍序列，如果当前节点入度不是0，就不是拓扑序列，加入结果集；统计入度的办法是，如果这个点已经扫过了就标记，如果这个点的所有入边节点没有被标记那肯定就是有效入度了，统计所有有效入度来判断这个节点的入度是不是0。

Code:

#include<bits/stdc++.h>
using namespace std;
#define inf 1009
#define INF 0x3f3f3f3f
#define loop(x,y,z) for(x=y;x<z;x++)

vector<int>node[inf];//入度
int n,m;
int book[inf];//标记
vector<int>ans;
void Solve()
{
    int i,j,k;
    scanf("%d%d",&n,&m);
    loop(i,0,m)
    {
        int v,u;
        scanf("%d%d",&v,&u);//v到u
        node[u].push_back(v);
    }
    int query;
    scanf("%d",&query);
    loop(i,0,query)
    {
        bool flag=true;//结果标记
        memset(book,0,sizeof book);
        loop(j,0,n)
        {
            int v;
            scanf("%d",&v);
            int len=node[v].size();
            int sum=0;//统计入度
            loop(k,0,len)
            {
                int u=node[v][k];
                if(!book[u])sum++;
            }
            if(sum)//sum!=0
                flag=false;
            book[v]=1;
        }
        if(!flag)
        ans.push_back(i);
    }
    //output
    int len=ans.size();
    printf("%d",ans[0]);
    loop(i,1,len)
        printf(" %d",ans[i]);
    printf("\n");
}
int main()
{
    Solve();
    return 0;
}