[2021 SCPC 1차 예선]
No Cycle
이 그래프에서 방향성이 있는 간선들만 고려했을 때 사이클이 존재하지 않는다.
방향성이 정해지지 않은 간선들의 방향을 모두 정하려고 하는데, 모두 정하고 나서도 그래프에 사이클이 존재하지 않아야 한다.
아래 예 들에서 화살표로 표시된 간선은 방향성이 있는 간선, 점선으로 표시된 간선은 방향성이 정해지지 않은 것이다. 정점 안의 수는 정점의 번호이다.
왼쪽의 경우 점선으로 표시된 간선의 방향성을 3번에서 2번으로 가는 것으로 정하면 사이클이 생기게 된다.
따라서 이 경우는 2번에서 3번으로 가는 것으로 방향성을 정해야 한다.
오른쪽의 경우 점선으로 표시된 간선의 방향성을 어떻게 정하더라도 사이클이 생기지 않는다.
방향성을 정할 수 있는 방법이 여러가지임에 주의하라.
위의 경우 점선으로 표시된 간선들의 방향성을 4번에서 1번, 2번에서 3번으로 정하는 경우를 제외하면 다른 모든 경우에서 사이클이 생기지 않는다.
방향성이 정해지지 않은 간선들의 방향성을 모두 정하되, 그래프에 사이클이 없도록 하는 프로그램을 작성하라.
간선의 방향성을 정해서 출력하는 방법이 복잡할 수 있으므로 아래 [입력]과 [출력] 부분을 주의 깊게 확인하기 바란다.
또, 사이클이 없도록 방향성을 정하는 방법이 여러가지인 경우에도 주의해서 답을 출력해야 한다.
- 제한시간: 전체 테스트 케이스는 70개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다. ※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다. - 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
- 제출 제한 : 최대 10회
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\)가 주어지고,
이후 차례로 \(T\)개의 테스트 케이스가 주어진다. \((1 ≤ T ≤ 70) \)
각 테스트 케이스의 첫 줄에는 정점의 개수 \(N\), 방향성 정해진 간선의 개수 \(M\), 방향성이 정해지지 않은 간선의 개수 \(K\)가 주어진다. \((\ 3≤N≤500,\ 0≤M≤2,000,\ 1≤K≤2,000\ )\)
정점들은 1번부터 \(N\)번까지 번호가 붙어 있다.
둘째 줄부터 \(M\)개의 각 줄에는 두 정점의 번호가 주어진다. 첫 정점에서 두번째 정점으로 방향이 있는 간선이 있다는 의미이다.
그 다음 \(K\)개의 각 줄에는 두 정점의 번호가 주어진다. 두 정점을 연결하는 방향이 정해지지 않은 간선이 있다는 의미이다. 이 간선들은 주어진 순서대로 번호가 붙어 있다.
하나의 정점을 간선이 연결하는 경우는 없으나, 동일한 쌍의 정점들에 대해 여러 개의 간선이 존재할 수 있다.
- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 180 점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (41 점) : 이 그룹의 테스트 케이스에서는 \(3≤N≤10,\ 0≤M≤20,\ 1≤K≤10\)이다.
ㆍ 그룹 2 (52 점) : 간선들에 방향을 부여할 수 있는 방법이 유일하다.
ㆍ 그룹 3 (87 점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
- 모든 테스트 케이스를 풀지 않고 일부분의 그룹에 속하는 테스트 케이스만을 푸는 경우에도 입력 받은 모든 케이스에 대해 (답이 틀릴지라도) 출력 양식에는 맞는 출력을 생성해야 점수가 반영되는 것이 보장된다.
- 제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며, 그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #\(C\)”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.
그 다음 줄에, 0과 1로 이루어진 문자열을 출력한다. 각 문자는 \(K\)개의 방향성이 정해지지 않은 간선들의 번호 순으로 0인 경우 입력에 주어진 순서 대로 방향을 부여했다는 의미이고 1은 그 반대로 방향을 부여했다는 의미이다. 가능한 답이 여러가지인 경우 사전순으로 가장 빠른 것을 출력하라.
입출력예
| 입력 |
|---|
| 2 3 3 1 1 2 2 3 1 3 3 1 4 2 2 1 2 3 4 2 3 4 1 |
| 출력 |
|---|
| Case #1 1 Case #2 01 |