热门标签 | 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

 


推荐阅读
  • 题目解析给定 n 个人和 n 种书籍,每个人都有一个包含自己喜好的书籍列表。目标是计算出满足以下条件的分配方案数量:1. 每个人都必须获得他们喜欢的书籍;2. 每本书只能分配给一个人。通过使用深度优先搜索算法,可以系统地探索所有可能的分配组合,确保每个分配方案都符合上述条件。该方法能够有效地处理这类组合优化问题,找到所有可行的解。 ... [详细]
  • IOS Run loop详解
    为什么80%的码农都做不了架构师?转自http:blog.csdn.netztp800201articledetails9240913感谢作者分享Objecti ... [详细]
  • 经过两天的努力,终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练,不仅加深了对半平面交算法的理解,还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题,进一步巩固和拓展相关知识。 ... [详细]
  • 零拷贝技术是提高I/O性能的重要手段,常用于Java NIO、Netty、Kafka等框架中。本文将详细解析零拷贝技术的原理及其应用。 ... [详细]
  • 本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题,重点在于单点更新和区间查询最大值。 ... [详细]
  • [转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]
  • Java高并发与多线程(二):线程的实现方式详解
    本文将深入探讨Java中线程的三种主要实现方式,包括继承Thread类、实现Runnable接口和实现Callable接口,并分析它们之间的异同及其应用场景。 ... [详细]
  • 检查在所有可能的“?”替换中,给定的二进制字符串中是否出现子字符串“10”带 1 或 0 ... [详细]
  • poj 3352 Road Construction ... [详细]
  • 开发技巧:在Interface Builder中实现UIButton文本居中对齐的方法与步骤
    开发技巧:在Interface Builder中实现UIButton文本居中对齐的方法与步骤 ... [详细]
  • 本报告对2018年湘潭大学程序设计竞赛在牛客网上的时间数据进行了详细分析。通过统计参赛者在各个时间段的活跃情况,揭示了比赛期间的编程频率和时间分布特点。此外,报告还探讨了选手在准备过程中面临的挑战,如保持编程手感、学习逆向工程和PWN技术,以及熟悉Linux环境等。这些发现为未来的竞赛组织和培训提供了 valuable 的参考。 ... [详细]
  • 在尝试对 QQmlPropertyMap 类进行测试驱动开发时,发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的,需要进一步研究以找到解决方案。 ... [详细]
  • 深入解析Android 4.4中的Fence机制及其应用
    在Android 4.4中,Fence机制是处理缓冲区交换和同步问题的关键技术。该机制广泛应用于生产者-消费者模式中,确保了不同组件之间高效、安全的数据传输。通过深入解析Fence机制的工作原理和应用场景,本文探讨了其在系统性能优化和资源管理中的重要作用。 ... [详细]
  • QT框架中事件循环机制及事件分发类详解
    在QT框架中,QCoreApplication类作为事件循环的核心组件,为应用程序提供了基础的事件处理机制。该类继承自QObject,负责管理和调度各种事件,确保程序能够响应用户操作和其他系统事件。通过事件循环,QCoreApplication实现了高效的事件分发和处理,使得应用程序能够保持流畅的运行状态。此外,QCoreApplication还提供了多种方法和信号槽机制,方便开发者进行事件的定制和扩展。 ... [详细]
  • 洛谷 P4035 [JSOI2008] 球形空间生成器(高斯消元法 / 模拟退火算法)
    本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案,主要使用了高斯消元法和模拟退火算法。通过这两种方法,可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码,适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内,确保了算法的高效性和准确性。 ... [详细]
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社区 版权所有