| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 202 | 11 | 10 | 9.434% |
정점 $N$개, 간선 $M$개로 이루어진 단순 무방향 그래프 $G=(V,E)$가 주어진다. 그래프의 정점은 $1$ 이상 $N$ 이하의 번호를 가지며, 간선 역시 $1$ 이상 $M$ 이하의 번호를 가진다. 이때 다음 조건에 맞는 $\{1,2,\cdots ,N\}$의 순열 $\pi$를 찾자.
첫째 줄에 정점의 개수 $N$, 간선의 개수 $M$이 공백으로 구분되어 주어진다.
둘째 줄부터 $M$개의 줄에 걸쳐 $i+1$번 줄에 $i$번 간선의 양 끝점 $u_i$, $v_i$가 공백으로 구분되어 주어진다.
조건에 맞는 순열이 존재한다면 그러한 순열을 출력한다. 조건에 맞는 순열이 여러 가지라면 어떤 것을 출력해도 상관없다.
조건에 맞는 순열이 존재하지 않는다면 -1을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N, M \le 10$ |
| 2 | 30 | $N, M \le 10^3$, 임의의 서로 다른 세 정점 $u$, $v$, $w$에 대해, 점 $u$에서 점 $v$를 거치지 않고 점 $w$로 이동하는 경로가 존재한다. |
| 3 | 10 | $N, M \le 10^3$ |
| 4 | 50 | 추가 제한 조건이 없다. |
4 4 1 2 2 3 3 4 4 2
1 2 4 3
7 10 2 1 3 1 3 2 4 1 4 3 5 3 5 4 6 3 7 5 7 6
1 4 5 7 6 3 2
7 9 2 1 3 1 3 2 4 3 5 3 5 4 6 4 6 5 7 6
1 2 3 5 4 6 7
4 3 1 4 2 4 3 4
-1
School > 서울과학고등학교 > SciOI 2023 A-4번