T46449 有向图无环(DAG)的判定 （dfs）

T46449 有向图无环(DAG)的判定
提交
172
通过
69
时间限制
1.00s
内存限制
125.00MB
提交答案
加入收藏
题目提供者
BDFZ-OIER
难度
暂无评定
历史分数
100
提交记录
标签
暂无标签
进入讨论版
相关讨论
暂无
推荐题目
展开
题目描述
给定无权有向图G(V,E)，请判断G是否是一个有向无环图（DAG）。

*在有向图中，若存在B边，则存在环。

输入格式
第一行包含两个整数N、M，表示该图共有N个结点和M条有向边。（N <= 5000，M <= 200000）

接下来M行，每行包含2个整数{u,v}，表示有一条有向边(u,v)

输出格式
有环输出“not DAG”，无环输出“DAG”

输入输出样例
输入 #1复制
5 7
1 2
1 5
2 3
3 1
3 2
4 1
4 5
输出 #1复制
not DAG

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int n,m;
const int maxn=5005;
int post[maxn],pre[maxn];
vector<int>adj[maxn];
template<class T>
void read(T &x){ll f=1;x=0;char c=getchar();while(!isdigit(c)){f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-48;c=getchar();}x*=f;
}
template<class T>
void write(T x){if(x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');
}
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int flag=1,t;
void dfs(int u){pre[u]=++t;for(auto i:adj[u]){if(!pre[i]){dfs(i);}else if(!post[i]){flag=0;}}post[u]=++t;
}
int main()
{  read(n);read(m);int a,b;for(int i=0;i<m;i++){read(a),read(b);adj[a].push_back(b);}for(int i=1;i<=n;i++){if(!pre[i])dfs(i);}if(flag)printf("DAG");else printf("not DAG");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！