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?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。