专栏首页CSDN旧文图论--拓扑排序--判断一个图能否被拓扑排序

图论--拓扑排序--判断一个图能否被拓扑排序

拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得到一个线性序列,实现的方式是DFS,具体的实现原理,我们将在下一篇博客中讲解。

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100+10;
int n,m;
vector<int> G[maxn];//G[i]表示i节点所指向的所有其他点
int in[maxn];//节点入度
bool topo()//判断该图是否可拓扑排序
{
    queue<int> Q;
    int sum=0;//记录可拆解的点数目
    for(int i=0;i<n;i++)if(in[i]==0)
        Q.push(i);
    while(!Q.empty())
    {
        int u=Q.front(); Q.pop();
        sum++;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in[v]==0) Q.push(v);
        }
    }
    return sum==n;//可完全拓扑
}
int main()
{
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        memset(in,0,sizeof(in));
        for(int i=0;i<n;i++) G[i].clear();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            in[v]++;
        }
        printf("%s\n",topo()?"YES":"NO");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图论--LCA--在线RMQ ST

    风骨散人Chiam
  • 图论--LCA--Tarjan(离线)

    风骨散人Chiam
  • 使用高级程序设计语言实现集合的交并差运算

    风骨散人Chiam
  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 指针详解(一)

    C语言可谓是因为指针而拥有了其他的语言所不拥有的作用,但是却又因为指针导致它对于初学者而言是一个很难克服的难题。接下来我们直切主体——指针。

    石的三次方
  • Leetcode 周赛题解 220

    给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。

    ACM算法日常
  • 一套帮助你理解C语言的测试题(转)

          原文链接:http://www.nowamagic.net/librarys/veda/detail/775

    xuyaowen
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • C语言实现计算器(指针+函数)

    输入两个整数a和b,及+,-,*,/中的任意一字符。根据输入字符对整数a和b做相应的算术运算,如输入+,程序就给出a与b之和,输入-,就给出a和b之差,输入*,...

    小Bob来啦
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack

扫码关注云+社区

领取腾讯云代金券