[SOJ] DAG?

Description

输入一个有向图，判断该图是否是有向无环图(Directed Acyclic Graph)。

Input

输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=100，0<=m<=10000。

接下来的m行，每行是一个数对u v，表示存在有向边(u,v)。顶点编号从1开始。 Output

如果图是DAG，输出1，否则输出0

Sample Input  Copy sample input to clipboard 3 3 1 2 2 3 3 1 Sample Output 0

//有向无环图至少又一个只有入边没有出边的点 #include<iostream> #include<memory> using namespace std;const int MAX = 102; int n, m; int edge[MAX][MAX]; bool isPoint[MAX];void find_Point() {for(int j=1;j<=n;j++){int sum=0;for(int i=1;i<=n;i++)sum+=edge[j][i];if(sum==0)isPoint[j]=true;} }bool isDAG() {for(int i=1;i<=n;i++)if(isPoint[i])return false;return true; }int main() {memset(isPoint, false, sizeof(isPoint));memset(edge, 0, sizeof(edge));cin>>n>>m;for(int i=1;i<=m;i++){int a, b;cin>>a>>b;edge[a][b]=1;edge[b][a]=1;}find_Point();if(!isDAG())cout<<"1"<<endl;else cout<<"0"<<endl;return 0; }

　　

转载于:https://www.cnblogs.com/KennyRom/p/6244493.html

总结

以上是生活随笔为你收集整理的[SOJ] DAG?的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。