동적 연결성
플래티넘 V의견: 0
\(N\)개의 정점이 있다. 처음에는 간선이 하나도 없다.
이후 \(Q\)개의 연산이 주어진다.
연산은 세 종류이다.
1 u v : 정점 \(u\)와 \(v\)를 잇는 간선을 추가한다.
2 u v : 정점 \(u\)와 \(v\)를 잇는 간선을 삭제한다.
3 u v : 현재 그래프에서 정점 \(u\)와 \(v\)가 연결되어 있는지 출력한다.
3 u v 연산마다 두 정점이 연결되어 있으면 YES, 아니면 NO를 출력하시오.
\(1 ≤ N ≤ 200\,000\)
\(1 ≤ Q ≤ 200\,000\)
\(1 ≤ u, v ≤ N\)
\(u ≠ v\)
첫째 줄에 정점의 개수 \(N\)과 연산의 개수 \(Q\)가 주어진다.
둘째 줄부터 \(Q\)개의 줄에 걸쳐 연산이 주어진다.
각 연산은 다음 중 하나의 형태이다.
1 u v
2 u v
3 u v
3 u v 연산이 주어질 때마다 정점 \(u\)와 \(v\)가 연결되어 있으면 YES, 아니면 NO를 한 줄에 하나씩 출력한다.
5 11
3 1 2
1 1 2
1 2 3
3 1 3
1 4 5
3 1 5
1 3 4
3 1 5
2 2 3
3 1 5
3 3 5NO
YES
NO
YES
NO
YES처음에는 간선이 없으므로 1과 2는 연결되어 있지 않다.
이후 1-2, 2-3 간선이 추가되면 1과 3은 연결된다.
그 뒤 3-4 간선이 추가되면 1-2-3-4-5가 모두 연결된다.
하지만 2-3 간선이 삭제되면 {1,2}와 {3,4,5}가 분리된다.
anthony0506 작성
출처 anthony0506
평가 및 의견
동적 연결성
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
동적 연결성