热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

判断有向图是否存在3元环并进行拓扑排序

题目大意:给你一个关系图,判断是否合法,每个人都有师父和徒弟,可以有很多个;但是你的师父不能是你徒弟的徒弟,或者说你的徒弟不能是你师父的师父,这是不合法的情况。简单理解就是:判断有

题目大意:

   给你一个关系图,判断是否合法,

  每个人都有师父和徒弟,可以有很多个;

  但是你的师父不能是你徒弟的徒弟,或者说你的徒弟不能是你师父的师父,这是不合法的情况。

  简单理解就是:判断有向图中是否存在3元环;

  此题至少有三种做法,此处跟新拓扑排序的做法:

1. 拓扑排序:

  1. 统计每个点的入度;

   2. 将入度为0的点加入队列;

    3. 出去队首元素,将此元素所连接的点入度减一,若此后入度为0则加入队列;

   4. 判断队列循环次数,若等于n则不存在3元环,则此关系图合法;

题目链接:

点击打开链接

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std;  
const int  N = 2005;
const int  M = 3000005;
int n,m;
int tot,flag;
int in[N],head[N];
struct lp
{
    int u,v,nex;
    lp(){}
    lp(int a,int b,int c):
    u(a),v(b),nex(c){}
}cw[N];
void add(int a,int b){
    cw[++tot]=lp(a,b,head[a]);
    head[a]=tot;
}
void tuopu(){
    queue<int>Q;
    while(!Q.empty())Q.pop();
    for(int i=0;ii){
        if(in[i]==0)Q.push(i);
    }
    int t=0;
    while(!Q.empty()){
        t++;
        int u=Q.front();Q.pop();
        for(int i=head[u];i!=-1;i=cw[i].nex){
            int v=cw[i].v;
            in[v]--;
            if(in[v]==0)Q.push(v);
        }
    }
    if(t==n)flag=1;
}
int main(int argc, char const *argv[])
{
    int a,b;
    while(~scanf("%d%d",&n,&m)&&(n)){
        memset(in,0,sizeof(in));
        tot=-1;
        memset(head,-1,sizeof(head));
        for(int i=0;ii){
            scanf("%d%d",&a,&b);
            add(a,b);
            in[b]++;
        }
        flag=0;
        tuopu();
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
View Code

 


推荐阅读
  • ZOJ 2760 - 最大流问题
    题目链接:How Many Shortest Paths。题目描述:给定一个包含n个节点的有向图,通过一个n*n的矩阵来表示。矩阵中的a[i][j]值为-1表示从节点i到节点j无直接路径;否则,该值表示从i到j的路径长度。输入起点vs和终点vt,计算从vs到vt的所有不共享任何边的最短路径数量。如果起点和终点相同,则输出无穷大。 ... [详细]
  • 题目描述:给定 n 把雨伞和 m 个人,t 分钟后开始下雨。求在每个人只能使用一把雨伞的情况下,最多有多少人可以拿到雨伞。 ... [详细]
  • 本文探讨了如何利用数组来构建二叉树,并介绍了通过队列实现的二叉树层次遍历方法。通过具体的C++代码示例,详细说明了构建及打印二叉树的过程。 ... [详细]
  • 本题要求计算从起点到终点所有最短路径的总权重,使用SPFA算法进行求解。 ... [详细]
  • C基本语法C程序可以定义为对象的集合,这些对象通过调用彼此的方法进行交互。现在让我们简要地看一下什么是类、对象,方法、即时变量。对象-对象具有状态和行为 ... [详细]
  • 3144:[Hnoi2013]切糕TimeLimit:10SecMemoryLimit:128MBSubmit:1261Solved:700[Submit][St ... [详细]
  • 题目描述墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令ÿ ... [详细]
  • 正文♦时间复杂度:\(\mathcal{O}(n)\)思维题,不需要建树。设数组\(a\)记录每一个节点是否尊重它的父节点,数组\(b\)记录是否有节点尊重它,特别的,叶子节点必然 ... [详细]
  • 多用户密码验证与加密登录系统
    本文介绍了一种基于多用户密码文件的加密登录方法,通过读取用户密码文件并使用简单的加密算法实现安全登录。文中详细描述了程序的设计思路及其实现过程。 ... [详细]
  • 本文主要解决了在编译CM10.2时出现的关于Samsung Exynos 4 HDMI HAL库中SecHdmiV4L2Utils.cpp文件的编译错误。 ... [详细]
  • HDU1085 捕获本·拉登!
    问题描述众所周知,本·拉登是一位臭名昭著的恐怖分子,他已失踪多年。但最近有报道称,他藏匿在中国杭州!虽然他躲在杭州的一个洞穴中不敢外出,但近年来他因无聊而沉迷于数学问题,并声称如果有人能解出他的题目,他就自首。 ... [详细]
  • A1166 峰会区域安排问题(25分)PAT甲级 C++满分解析【图论】
    峰会是指国家元首或政府首脑之间的会议。合理安排峰会的休息区是一项复杂的工作,理想的情况是邀请的每位领导人都是彼此的直接朋友。 ... [详细]
  • 2022年4月15日的算法练习题,包括最长公共子序列和线段树的应用。 ... [详细]
  • 本文详细介绍了Oracle RMAN中的增量备份机制,重点解析了差异增量和累积增量备份的概念及其在不同Oracle版本中的实现。通过对比两种备份方式的特点,帮助读者选择合适的备份策略。 ... [详细]
  • 本文详细探讨了如何处理包含多种分隔符的字符串分割问题,并提供了一个高效的C++实现方案。 ... [详细]
author-avatar
开在覀黎明前的小茉莉
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有