[백준] 1412 일방통행

X에서 출발해 X로 돌아올 수 있는지 없는지 판단하는 문제다

Cycle이 있으면 안되는 문제다.

하지만 양방향 간선끼리의 Cycle은 방향을 알아서 지정하면 되므로 

문제가 안된다..!

따라서 양방향인 간선들은 무시하고 단방향인 간선들로 그래프를 그린다

그리고 Cycle을 찾으면 된다!

Cycle을 찾는 함수를 사용해도 괜찮고 플로이드를 써도 괜찮다!

소스코드(Cycle detect)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, arr[111][111], check[111];
vector<vector<int>> Graph;
bool isCycle(int x) {
    if (check[x]) {
        if (check[x] == 1) return false;
        return true;
    }
    check[x] = -1;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (isCycle(next)) return true;
    }
    check[x] = 1;
    return false;
}
int main() {
    scanf(" %d", &n);
    Graph.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char a; scanf(" %1c", &a);
            if (a == 'Y') arr[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] && arr[j][i] && i != j || !arr[i][j]) continue;
            Graph[i].push_back(j);
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (check[i]) continue;
        if (isCycle(i)) {
            puts("NO"); return 0;
        }
    }
    puts("YES");
}

플로이드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, arr[111][111], d[111][111];
 
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char a; scanf(" %1c", &a);
            if (a == 'Y') arr[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] && arr[j][i] && i !=j || !arr[i][j]) continue;
            d[i][j] = 1;
        }
    }
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][k] && d[k][j]) d[i][j] = 1;
            }
        }
    }
    for(int i=0;i<n;i++)
        if (d[i][i]) {
            puts("NO"); return 0;
        }
    puts("YES");
}