레이팅 미적용어떤 심리학자는 학교의 학급이나 회사의 부서와 같이 여러 사람들이 모인 집단이 어떤 경우에 안정되어 있는지를 연구하였다. 심리학자는 집단에 속한 모든 사람들이 서로 좋아하거나 혹은 그 집단이 여러 개의 소집단으로 나누어져 각 소집단 내에 있는 사람들끼리는 모두 서로 좋아하고 서로 다른 소집단에 속한 사람들끼리는 모두 서로 싫어한다면 그 집단은 안정되어 있다는 사실을 발견하였다. 단, 소집단은 적어도 2명 이상의 사람들로 구성되어야 한다. 예를 들면, 어떤 한 사람을 좋아하는 사람이 아무도 없다면 이 집단은 안정된 집단이 아니다.
\(n\)명으로 구성된 집단에서 사람들을 1번부터 \(n\)번까지 번호를 붙이고 서로 좋아하는 관계인지 아니면 싫어하는 관계인지를 조사하여 서로 좋아하면 0으로 나타내고 서로 싫어하면 1로 나타낸다. 집단 내의 모든 사람들 사이에 이러한 관계가 주어져 있을 때 여러분들은 이 집단이 안정되어 있는지 혹은 그렇지 않은지를 판단하고, 안정되어 있을 경우에는 한 개의 집단인지 혹은 여러 대의 소집단들로 분할되는지를 알아내야 한다.
< 그림 1 >과 같은 경우에 집단 {1, 2, 3, 4, 5}를 소집단 {1, 4, 5}와 {2, 3}으로 분할했을 때 각 소집단에 속한 사람들끼리는 모두 서로 좋아하고 서로 다른 소집단에 속한 사람들끼리는 모두 서로 싫어하므로 안정된 집단이라고 볼 수 있다.
첫째 줄에는 집단에 속한 사람들의 수 \(n(2 \le n \le 100)\)이 나타나있다. 둘째 줄부터 시작하여 \(n\)개의 줄에는 번호 순서대로 각 사람들이 다른 사람들을 좋아하는지 혹은 싫어하는지에 따라 순서대로 0 혹은 1의 값이 주어진다. 각 사람들은 자기 자신을 좋아한다고 가정한다. 그리고, 0과 1사이는 빈칸이 하나씩 있다.
주어진 입력이 안정되지 않은 집단의 경우는 첫줄에 빈칸 없이 0을 출력한다. 안정된 집단의 경우는 첫줄에 서로 좋아하는 소집단의 수를 빈칸 없이 출력하고, 그 다음 줄부터는 각 줄마다 각 소집단에 속하는 사람의 번호를 빈칸 하나에 의해 분리하여 출력한다. 출력 순서는 소집단 내에서는 번호의 오름차순으로 출력하고, 소집단 간에는 그 소집단에 속하는 제일 작은 번호의 오름차순으로 출력한다.
5
0 1 1 0 0
1 0 0 1 1
1 0 0 1 1
0 1 1 0 0
0 1 1 0 0
2
1 4 5
2 3
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 1998 > 2차 대회 > 중등부 1번