깜빡이는 연결망
다이아몬드 IV의견: 0
\(N\)개의 정점과 시간에 따라 나타났다 사라지는 간선들로 이루어진 무방향 그래프가 있다. 처음에는 간선이 하나도 없다.
\(M\)개의 이벤트가 순서대로 주어진다. 각 이벤트는 다음 중 하나이다.
-
1 u v: 정점 \(u\)와 \(v\) 사이에 간선을 추가한다. (이 시점에 같은 간선은 존재하지 않음이 보장된다) -
2 u v: 정점 \(u\)와 \(v\) 사이의 간선을 제거한다. (이 시점에 그 간선이 존재함이 보장된다) -
3 u v: 현재 \(u\)와 \(v\)가 (직접 또는 간접으로) 연결되어 있으면1, 아니면0을 출력한다.
간선이 추가/삭제되므로 단순한 유니온 파인드만으로는 처리할 수 없다.
\(1 \le N \le 100{,}000\)
\(1 \le M \le 120{,}000\)
\(1 \le u, v \le N\)
추가/제거되는 간선은 항상 \(u \ne v\)이다.
첫 줄에 두 정수 \(N\), \(M\)이 주어진다.
이어서 \(M\)개의 줄에 위 형식의 이벤트가 한 줄에 하나씩 주어진다.
각 3번 이벤트에 대해 연결 여부(\(1\) 또는 \(0\))를 한 줄에 하나씩 출력한다.
4 6
1 1 2
3 1 3
1 2 3
3 1 3
2 2 3
3 1 3
0
1
0간선 1-2 추가 후 1과 3은 분리 -> 0. 간선 2-3 추가 후 1-2-3 연결 -> 1. 간선 2-3 제거 후 다시 분리 -> 0.
2 4
3 1 1
1 1 2
2 1 2
3 1 2
1
0자기 자신과는 항상 연결 -> 1. 간선을 추가했다 바로 제거하면 1과 2는 분리 -> 0.
riseoj 작성
출처 Original
평가 및 의견
깜빡이는 연결망
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
깜빡이는 연결망