문제
희주는 스포츠기사를 쓰는 기자이다. 어제까지 k리그의 대회가 있었다. 대회는 n개의 축구팀 풀리그 방식으로 경기를 하였다. 그 결과 다음과 같이 경기 결과의 정보를 부분적으로 알 수 있었다.
정보1. 무승부는 없었다. 정보2. 각 팀은 각 순위가 부여되었다. 정보3. a번째 팀이 b번째 팀을 이겼다.
희주는 알고 있는 경기의 결과와 위 3가지 정보를 가지고 각 팀의 순위를 정하여 기사를 쓰려고 한다.
입력
입력의 첫줄에는 축구팀의 개수 n(1≤n≤5,000)이 주어지며 1부터 n까지 팀의 번호가 매겨진다. 두 번째 줄에는 알고 있는 경기 결과의 수 m(1≤n≤100,000))이 주어진다. 그 다음 줄부터 n개의 줄에 걸쳐 경기 결과 a, b(1≤a, b≤n)가 들어온다.
출력
출력은 n+1줄로 구성되며, 1~n줄에는 순서대로 팀의 순위가 출력되고, n+1줄에는 또 다른 순위를 정할 수 있으면 1을 그렇지 않으면 0을 출력한다.
예제 #1
4
5
1 2
3 1
3 2
3 4
4 1
3
4
1
2
0
첫번째 예제를 팀번호 별로 경기의 결과 테이블을 만들어보면
a팀과 b팀의 결과로 o-승, x-패, ?-결과를 모른다. 위의 결과대로 순위를 구하면 다음과 같다.
예제 #2
3
2
2 1
2 3
2
1
3
1
두번째 예제를 팀번호 별로 경기의 결과 테이블을 만들어보면
위의 결과대로 순위를 구하면 다음과 같다.
이 경우는 2가지의 순위를 정할 수 있는 것을 알 수 있다. (즉, 2 3 1 1을 출력해도 정답으로 처리한다.)
출처
JOI 2007 #4
로그인해야 코드를 작성할 수 있어요.