소문의 전파
골드 III의견: 0
학교에 \(N\)명의 학생이 있다. 학생들 사이에 \(M\)개의 단방향 관계가 있어, '\(A\)가 \(B\)에게 직접 소문을 전달할 수 있다'는 관계가 주어진다. 소문은 연쇄적으로 전달될 수 있다.
즉, \(A\)에서 \(C\)로 소문이 전달되려면 \(A\to B_1\to B_2\to \cdots\to C\)와 같이 한 명 이상 거쳐 전달하는 것도 허용된다. 단, 본인에서 본인으로의 전달은 항상 가능하다(\(A\to A\)).
\(Q\)개의 질문 \((s, t)\)에 대해 학생 \(s\)가 학생 \(t\)에게 소문을 전달할 수 있으면 \(1\), 없으면 \(0\)을 출력하여라.
- \(1 \le N \le 100\)
- \(0 \le M \le N(N-1)\)
- \(1 \le Q \le 10\,000\)
- \(1 \le A, B \le N\), \(A \ne B\)
- \(1 \le s, t \le N\) (단, \(s = t\)도 가능)
첫째 줄에 학생 수 \(N\), 관계 수 \(M\), 질문 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 단방향 관계 \(A\), \(B\)가 주어진다 (\(A\)가 \(B\)에게 직접 전달 가능).
다음 \(Q\)개의 줄에 질문 \(s\), \(t\)가 주어진다.
\(Q\)개의 줄에 걸쳐, 각 질문에 대해 전달 가능하면 \(1\), 불가능하면 \(0\)을 출력한다.
5 4 4
1 2
2 3
3 4
4 5
1 5
5 1
2 5
3 1
1
0
1
0
학생 \(1\to2\to3\to4\to5\) 방향으로 연결되어 있다. \(1\)에서 \(5\)까지는 소문이 전달되지만(\(1\)), \(5\)에서 \(1\)로는 전달되지 않는다(\(0\)). \(3\)에서 \(1\)로도 전달 불가(\(0\)).
4 3 6
1 2
2 1
3 4
1 2
2 1
1 3
3 1
1 4
4 3
1
1
0
0
0
0
학생 \(1\)과 \(2\)는 서로 소문을 전달할 수 있다. \(3\)과 \(4\)도 연결되어 있지만 \(\{1,2\}\)에서 \(\{3,4\}\)로, 또는 그 역방향으로는 전달 불가.
riseoj 작성
출처 Original
평가 및 의견
소문의 전파
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
소문의 전파