?? 判斷有向圖是否有環(huán).txt
字號:
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define NMAX 105
int path[NMAX][NMAX];
int Ingree[NMAX];//各個點的入度
//判斷一個有向圖是否有環(huán)
/*
輸入:
4
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
5
0 1 0 0 0
0 0 1 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 0
4
0 1 0 0
0 0 1 1
0 0 0 1
0 0 0 0
輸出:
yes
no
yes
no
*/
void getIn(int num)
{ //計算各個點的入度
int j,sum,i;
for(i=1;i<=num;i++)
{
sum=0;
for(j=1;j<=num;j++)
if(path[j][i]==1) sum++;
Ingree[i]=sum;
}
}
int cal(int num)
{ //使用拓撲排序的方法判斷是否有環(huán)
int i,k,now,count=0;
int stack[NMAX];
k=0;
getIn(num);
for(i=1;i<=num;i++)
if(Ingree[i]==0) stack[k++]=i;//入度為0的點入棧
while(k!=0)//棧不為空
{
now=stack[--k];//將棧里元素A出棧
count++;//符合拓撲序列的元素個數加1
for(i=1;i<=num;i++)
{
if(path[now][i]==1)
{
Ingree[i]--;//A元素指向的所有的點入度減1
if(Ingree[i]==0) stack[k++]=i;//如果入度為0,再入棧
}
}
}
if(count<num) return 1;//不是所有的點符合拓撲序列,說明存在環(huán)
else return 0;
}
int main()
{
int num,i,j;
while(scanf("%d",&num)!=EOF)
{
for(i=1;i<=num;i++)
{
for(j=1;j<=num;j++)
scanf("%d",&path[i][j]);
}
if(cal(num)==1) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -