시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 381 | 48 | 32 | 14.953% |
학생들은 스타 대회를 열기로 했다. 참가자는 총 N명으로 1번부터 N번까지 번호가 붙어있다. 토너먼트의 규칙은 다음과 같다. 게임이 진행되는 동안 남아있는 참가자 중 임의의 두 명을 뽑아 스타를 붙인다. 경기 후 패자는 탈락되고 승자는 계속해서 대회에 참가하게 된다. (단, 무승부는 존재하지 않는다.) 결국 N-1번의 게임을 하면 최후의 승자가 남게 되고 이 학생이 우승을 하게 된다.
참가자 중 어떤 한 학생이 다른 한 학생을 항상 이기는 천적 관계가 존재한다. 즉, 이 두 학생끼리는 경기를 펼치지 않아도 누가 이긴다는 것을 알 수 있다는 것이다. 예를 들어, 위와 같은 그래프에서 1번은 2, 3번을 항상 이긴다는 뜻이다. 하지만 1번과 4번이 경기하면 1번이 이길 수도 있고 4번이 이길 수도 있다.
N명의 참가자에 대한 천적 관계가 주어졌을 때 우승 가능성이 있는 학생들을 알 수 있다. 예를 들어, 위의 예에서 3번 학생은 1번 학생한테 항상 지지만 4번 학생과 1번 학생이 경기를 하여 1번 학생이 탈락한 후 3번 학생이 2, 4번 학생을 차례대로 이기고 우승할 수 있기 때문에 우승 가능성이 있는 학생이다.
문제는 N명의 참가자에 대한 천적 관계가 주어지면 우승 가능성이 있는 학생들을 모두 구하는 것이다.
첫째 줄에 참가자 수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에 천적관계가 주어지는데 i+1번째 줄에는 i번째 학생이 항상 이기는 학생의 수 와 이 학생들의 번호가 공백으로 구분되어 증가하는 순서로 주어진다. (단, 자기 자신이 천적인 경우는 없다.) 천적 관계의 총 수는 1,000,000을 넘지 않는다.
첫째 줄에 우승 가능성이 있는 학생 수 w와 이 학생들의 번호를 오름차순으로 공백으로 구분하여 출력한다.
4 2 2 3 0 1 2 1 2
3 1 3 4
Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 2 5번