아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

사이클 탐지

시간 제한1초메모리 제한128 MB

요약
정점이 20개 이하인 그래프에서 사이클에 속하는 각 간선마다 그 간선을 포함하는 서로 다른 단순 사이클의 개수를 센다.
난이도

보통10점 중 7점

유형
그래프, 완전 탐색, 비트 연산, DFS
정답자
아직 제출이 없습니다

문제

컴퓨터들이 케이블로 연결된 네트워크가 있습니다. 각 케이블은 정확히 두 대의 컴퓨터를 연결하며, 두 컴퓨터 사이에는 케이블이 최대 한 개만 존재합니다.

주어진 네트워크에서 사이클에 포함되는 모든 케이블을 찾고, 각 케이블마다 그 케이블이 몇 개의 사이클에 포함되는지 구하세요.

사이클이란 어떤 컴퓨터 AA에서 출발하여 다시 AA로 돌아오는 케이블의 나열입니다. 단, AA를 제외한 나머지 컴퓨터는 사이클 안에서 한 번씩만 등장해야 합니다. 케이블의 집합이 같다면, 방향이나 시작 컴퓨터가 달라도 하나의 사이클로 셉니다.

입력

첫째 줄에 네트워크에 있는 컴퓨터의 수를 나타내는 양의 정수 NN (N≤20N \le 20)이 주어집니다.

다음 NN개의 줄에는 컴퓨터 사이의 연결 상태가 인접 행렬 형태로 주어집니다. 각 줄에는 공백으로 구분된 NN개의 값이 있습니다. LL번째 줄 CC번째 열의 값이 00이면 컴퓨터 LL과 CC 사이에 직접 연결이 없다는 뜻이고, 그렇지 않으면 두 컴퓨터가 직접 연결되어 있다는 뜻입니다.

출력

첫째 줄에 적어도 하나의 사이클에 포함되는 케이블의 수 MM을 양의 정수로 출력합니다.

그다음 줄에는 각 케이블이 포함되는 사이클의 개수를 나타내는 MM개의 양의 정수를 공백으로 구분하여 출력합니다. 이 수열은 오름차순으로 정렬되어야 합니다.

사이클에 포함되는 케이블이 하나도 없다면 NO CYCLE 한 줄만 출력합니다.

예제4

  1. 예제 1

    입력
    6
    0 1 1 0 0 0
    1 0 1 1 0 0
    1 1 0 0 0 1
    0 1 0 0 1 0
    0 0 0 1 0 1
    0 0 1 0 1 0
    
    예상 출력
    7
    2 2 2 2 2 2 2
    
  2. 예제 2

    입력
    3
    0 1 1
    1 0 1
    1 1 0
    
    예상 출력
    3
    1 1 1
    
  3. 예제 3

    입력
    4
    0 1 0 1
    1 0 1 0
    0 1 0 1
    1 0 1 0
    
    예상 출력
    4
    1 1 1 1
    
  4. 예제 4

    입력
    4
    0 1 0 0
    1 0 1 0
    0 1 0 1
    0 0 1 0
    
    예상 출력
    NO CYCLE