11581 - 구호물자

https://www.acmicpc.net/problem/11581

2015 인하대학교 프로그래밍 경시대회 G번

처음에는 BFS를 돌면서 다시 방문하는 정점이 있는 경우 NO CYCLE을 출력하고 끝내려했는데, 코딩 미스인건지 오답을 맞았다. (이거 BFS로는 안되는건가요? 누가 댓글로 답변 바람) (참고로 다들 DFS로 푼 것 같다..)

딱히 좋은 아이디어는 안 떠올라서 플로이드 와샬로 정점과 정점이 이동 가능한지 저장했다. 그리고 1번 정점에서 $i$번 정점까지 방문 가능한 것들 중에 $i$번 정점에서 $i$번 정점으로 다시 돌아올 수 있는 (싸이클이 생기는) 경우가 있다면 CYCLE을 출력하도록 했다.

입출력 몇 개를 예로 적어놔야겠다.

예제 #1

6
2 2 3
2 4 6
1 4
1 5
1 3

CYCLE

예제 #2

6
2 2 6
1 6
1 4
2 2 5
1 3

NO CYCLE

#include <bits/stdc++.h>
using namespace std;

int main(){
    int i, j, k, n, m;
    bool v[101][101]={};
    scanf("%d", &n);
    for(i=0; i<n-1; ++i){
        scanf("%d", &m);
        while(m--){
            scanf("%d", &k);
            v[i][k-1] = true;
        }
    }
    for(k=0; k<n; ++k){
        for(i=0; i<n; ++i){
            for(j=0; j<n; ++j){
                v[i][j] |= v[i][k] & v[k][j];
            }
        }
    }
    bool cycle = false;
    for(i=0; i<n-1; ++i){
        cycle |= v[0][i] && v[i][i];
    }
    if(!cycle) printf("%s ", "NO");
    puts("CYCLE");
    return 0;
}