判断一个有向图是否有环

- 日理万妓 2022-04-22 06:50 201阅读 0赞

## Description ##

给出一个有向图，判断图中是否存在回路。

## Input ##

第 1 行：输入图的顶点个数 N （ 1  ≤  N ≤  2,500 ）和 C （图的边数， 1  ≤  C  ≤  6,200 ）；

第 2 到 C+1 行中，第 i+1 行输入两个整数，分别表示第 i 条边的起点和终点的编号。

## Output ##

如果图中存在回路，输出“ YES ”，否则，输出“ NO ”。

## Sample Input ##

7 8

1 2

1 3

2 4

2 6

3 4

4 5

5 2

5 7

## Sample ##

YES

大致的思路是深搜，将深搜的点加一个特殊标记，如果从当前的点往下搜的时候，发现了这个特殊标记，立刻判定有环。

代码如下

#include<cstdio>
    #include<cstring>
    int n,c,a[2600][2600],vis[2600],swi;
    int dfs(int v){    
        vis[v] = -1;    
        for(int i = 1; i <= n; i++)    
        {        
            if(a[v][i] != 0 && !vis[i])  {          
                dfs(i);        
                vis[i]=1;
            }
            if(a[v][i] != 0 && vis[i] == -1){     
                printf("YES\n");
                swi=true;
                return true;    
            }
        }    
        return false;
    }
    int main(){
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        swi=false;
        scanf("%d %d",&n,&c);
        int r1,r2;
        for(int i=0;i<c;++i){
            scanf("%d %d",&r1,&r2);
            a[r1][r2]=1;
        }
        dfs(1);
        if(!swi) printf("NO\n");
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关判断是否有环

1、给出两个单向链表的头指针pHead1和pHead2，判断这两个链表是否相交。假设两个链表均不带环。示意图如下： ![1337416819_7298.jpg][]

电玩女神/ 2024年02月19日 13:28/ 0 赞/ 15 阅读

相关【图】使用邻接表判断有向图和无向图中是否有环（Java 实现）

需求判断给定的图中是否有环本文研究有向图及无向图两种情况分析 1、当图中边的数量大于节点数量时，必然存在环； 2、当图中边的数量小于等于节点是，

骑猪看日落/ 2023年10月08日 22:48/ 0 赞/ 20 阅读

相关两种方式判断有向图是否有环-python实现

1. DFS判断有向图是否有环假设图以邻接矩阵表示，一条深度遍历路线中如果有结点被第二次访问到，那么有环。我们用一个变量来标记某结点的访问状态（未访问，访问过，其后结点

r囧r小猫/ 2023年08月17日 16:03/ 0 赞/ 90 阅读

相关判断图有无环_【转】判断一个图是否有环无向图有向图

无向图：法1：如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。 n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它

Myth丶恋晨/ 2023年01月10日 05:13/ 0 赞/ 123 阅读

相关判断一个有向图是否存在回路

判断一个有向图是否存在回路，除了采用拓扑算法以外，还可以使用深度优先搜索算法，本算法改编自“用邻接矩阵表示的深度优先搜索算法”，即DFS算法，两者共同点均为递归调用,DFS算法

喜欢ヅ旅行/ 2022年12月28日 00:56/ 0 赞/ 91 阅读

相关判断有向图是否有环及拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)

旧城等待，/ 2022年08月03日 13:39/ 0 赞/ 166 阅读

相关判断一个有向图是否有环

转自：http://blog.csdn.net/panhe1992/article/details/8366466 Description 给出一个有向图，判

今天药忘吃喽~/ 2022年06月14日 04:57/ 0 赞/ 148 阅读

相关判断图是否有环

总结一下判断图是否有环的所有方法，先只给出描述，后面有时间之后给出代码实现。一、无向图方法1、我们知道对于环1-2-3-4-1，每个节点的度都是2，基于此我们有如

系统管理员/ 2022年05月16日 04:47/ 0 赞/ 260 阅读

相关判断一个有向图是否有环

Description 给出一个有向图，判断图中是否存在回路。 Input 第 1 行：输入图的顶点个数 N （ 1 ≤ N ≤ 2,500 ）和 C （图

- 日理万妓/ 2022年04月22日 06:50/ 0 赞/ 202 阅读

相关判断一个图里是否有环

题目：利用并差集（disjoint\_set)判断一个图里是否有环 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

电玩女神/ 2021年12月12日 22:31/ 0 赞/ 206 阅读