📝 문제 정보#
문제 번역#
바이킹 락 운동에는 다양한 흐름이 존재한다. 올드 아이슬란드 그래니트 락, 미들 데니쉬 더스티 바이킹 락, 레이트 핀게일 다크 그린 락, 피오르드 볼더 아발란체 락 등, 인기 있는 흐름의 전체 목록을 나열하면 이 페이지를 여러 번 가득 채울 정도이다. 스칸디나비아 고등교육부는 이러한 흐름들이 서로 어떻게 영향을 주는지 연구하고 있다. 그들은 현재 대규모 실험을 계획 중이며, 적절히 선발된 자원봉사자들을 무인도들로 구성된 군도에 배치하여 상대적으로 긴 시간 동안 그들의 음악적 스타일과 선호도가 서로 미치는 영향을 관찰하고자 한다.
동일한 섬에 사는 사람들은 항상 서로 영향을 미친다. 일부 섬 쌍은 거리가 충분히 가까워 직접적인 영향이 가능하지만, 다른 섬 쌍은 거리가 멀어 직접적인 영향이 불가능하다. 후자의 경우에도, 영향력을 전달할 수 있는 하나 이상의 다른 거주 중인 섬이 있다면 간접적으로 영향을 주고받을 수 있다.
자원봉사자들을 섬에 배치하는 여러 제안들이 있다. 각 제안에 대해 교육부는 군도에 형성될 독립적인 거주자 그룹의 수를 알고 싶어 한다. 하나 이상의 섬을 차지하는 두 거주자 그룹은, 간접적인 방식을 포함하여 상호 영향의 가능성이 전혀 없을 때 독립적이라고 간주한다.
교육부의 제안 평가를 도와라.
입력#
첫 번째 줄에 세 정수 $N, E, P$ ($1 \le N \le 10^5, 0 \le E \le 10^5, 1 \le P \le 10^5$)가 주어진다. $N$은 군도의 섬 개수, $E$는 직접적인 영향이 가능한 섬 쌍의 개수, $P$는 평가할 제안의 개수이다. 섬은 1부터 $N$까지 번호가 매겨져 있다.
다음 $E$개의 줄에는 직접적인 상호 영향이 가능한 두 섬의 번호 $A, B$가 주어진다. 동일한 섬 쌍은 중복해서 주어지지 않는다.
다음 $P$개의 줄에는 각 제안의 정보가 주어진다. 각 줄은 해당 제안에서 사람이 거주하는 섬의 개수 $M$ ($1 \le M \le N$)으로 시작하며, 이어서 서로 다른 $M$개의 섬 번호가 주어진다. 그 외의 섬에는 사람이 살지 않는다.
모든 제안의 $M$값의 총합은 $10^5$을 넘지 않는다.
출력#
각 제안에 대해, 형성되는 독립적인 그룹의 수를 각 줄에 출력한다.
🧐 관찰 및 접근#
- 어떤 무향 그래프가 있고, 각 쿼리가 살아있는 정점만을 말할때 컴포넌트의 개수 구하기
- 온라인 단절점? ㅋㅋ는 미친거같고
- 각 정점에 대해 오프라인 쿼리…도 까다롭다.
- 어떤 제안들에 대해 살아있는 정점을 증가하게 만들 수 있다면?
- 그런것들은 한번에 처리해도 된다.
- 그데 그러면 문제가 되는상황은..
- $(1, 2, 3, 4, 5, 6, 7, 8, 9)$
- $(1, 2, 3, 4, 5, 6, 7, 8, 10)$
- $(1, 2, 3, 4, 5, 6, 7, 8, 11)$
- 이런식으로 있으면 재활용을 하기가 상당히 곤란한 문제가…
- 유파 롤백같은걸로 하면 되긴 하는데, 그러면 집합들을 어떻게 묶어줘야 하지? 어떤 순서로 처리해야 하지?
- 나이브하게 한다고 생각해보자.
- 결국 쿼리 하나당 $u \in P$에 대해, $\sum \text{deg}(u)$ 만큼의 시간복잡도가 걸린다.
- 그러니까, $\text{deg}(u)$만 작으면 문제가 없는데..
- $\text{deg}(u)$는 얼마나 클 수 있을까?
- $E \leq 10^5$이므로, $\text{deg}(u)$가 충분히 큰 정점 $u$가 많기는 어렵다.
- $deg(u) \times k \leq 10^5$ 여야 하므로!
- 따라서, 루트질을 시도해볼 수 있겠다. 간선이 많은 정점들에 대해서는 간선이 아닌 쿼리 내 정점들을 둘러보자.
- $E \leq 10^5$이므로, $\text{deg}(u)$가 충분히 큰 정점 $u$가 많기는 어렵다.
- 결국 쿼리 하나당 $u \in P$에 대해, $\sum \text{deg}(u)$ 만큼의 시간복잡도가 걸린다.
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> E >> P;
rep(i, 0, E){
int u, v; cin >> u >> v;
links[u].push_back(v);
links[v].push_back(u);
}
rep(i, 1, N+1){
links[i].push_back(N+1);
sort(all(links[i]));
}
rep(i, 1, N+2) toIdx[i] = -1;
while(P--){
int cnt; cin >> cnt;
vector<int> island(cnt);
rep(i, 0, cnt) cin >> island[i];
int idx = 0;
for(auto x: island) toIdx[x] = idx++;
UnionFind UF(cnt);
vector<int> skipped, hubo;
for(auto u: island){
if(links[u].size() < sq){
for(auto v: links[u]) if(toIdx[v] != -1) UF.merge(toIdx[u], toIdx[v]);
}
else skipped.push_back(u);
}
for(auto x: island) if(UF.find(toIdx[x]) == toIdx[x]) hubo.push_back(x);
for(auto u: skipped) for(auto v: hubo) if(*(lower_bound(all(links[u]), v)) == v){
UF.merge(toIdx[u], toIdx[v]);
}
cout << UF.group << '\n';
for(auto x: island) toIdx[x] = -1;
}
}