判断一个有向图是否有环

- 日理万妓 2022-04-22 06:50 236阅读 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 条评论，236人围观）

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

相关阅读

相关判断是否有环

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

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

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

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

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

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

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

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

相关有向图(3)--寻找有向环

在和有向图相关的实际应用中，有向环特别重要。从原则上来说，一幅有向图可能含有大量的环，在实际应用中，我们一般只会重点关注其中一小部分，或者只想知道它们是否存在。思路：一

一时失言乱红尘/ 2022年08月18日 02:35/ 0 赞/ 173 阅读

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

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

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

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

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

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

相关判断图是否有环

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

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

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

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

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

相关判断一个链表是否有环

判断一个链表是否有环方法一方法二方法三给出一个单向链表，判断链表中是否存在环。虽然是一个实际工作中基本不会碰到的场景，但是面试

骑猪看日落/ 2022年04月04日 14:27/ 0 赞/ 247 阅读

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

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

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