程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NOJ1119 仙林鼎山游樂園

NOJ1119 仙林鼎山游樂園

編輯:C++入門知識

NOJ1119 仙林鼎山游樂園


題意

給定一個有向無權圖,問圖中是否有環。

思路

用Floyd的形式進行預處理。eg[i][j]不僅僅表示有一條邊連著i和j,而表示有一條i到j的路。
這樣處理之後遍歷所有的情況,如果發現正著和反著都可以,那就是存在環了。

代碼

#include 
const int maxn = 55;
int n;
bool eg[maxn][maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--) {
        for(int i = 0 ; i < maxn ; i ++) {
            for(int j = 0 ; j < maxn ; j ++) eg[i][j] = false;
        }
        int c;
        scanf("%d%d",&n,&c);
        while(c--) {
            int a,b;
            scanf("%d%d",&a,&b);
            eg[a][b] = true;
        }
        for(int k = 0 ; k < n ; k ++) {
            for(int i = 0 ; i < n ; i ++) {
                for(int j = 0 ; j < n ; j ++) {
                    if(eg[k][i] && eg[i][j]) eg[k][j] = true;//所有可能的路都已經顯示出來了
                }
            }
        }
        bool flag = false;
        for(int i = 0 ; i < n ; i ++) {
            for(int j = 0 ; j < n ; j ++) {
                if(eg[i][j] && eg[j][i]) {
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved