NOJ1119 仙林鼎山游樂園

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;
}