📝 문제 정보#
문제 번역#
JOI 연방국에는 1부터 N까지 번호가 매겨진 N개의 도시와, 1부터 M까지 번호가 매겨진 M개의 도로가 있다. 도로 i (1 ≦ i ≦ M)는 도시 Ui와 도시 Vi를 양방향으로 연결하고 있다.
JOI 연방국은 1부터 K까지 번호가 매겨진 K개의 주(州)로 이루어져 있다. 도시 j (1 ≦ j ≦ N)는 주 Sj에 속해 있다. 또한, 모든 주는 적어도 하나의 도시를 포함한다.
JOI 연방국의 산업부 장관인 K 이사장은 앞으로 Q번의 교역을 진행하고자 한다. k번째 교역 (1 ≦ k ≦ Q)은 도시 Ak에서 도시 Bk까지 몇 개의 도로와 도시를 거쳐 특산품을 운송하는 것이다. 단, 이 교역에 협력해주는 곳은 주 SAk와 주 SBk만이며 (SAk = SBk인 경우는 주 SAk만), 이들 주에 속하지 않은 도시를 거치면 특산품을 도둑맞게 된다.
K 이사장은 특산품을 도둑맞지 않고 교역을 수행할 수 있는 운송 경로가 있는지 알아보고 싶어 한다. 도시와 도로의 배치, 주와 교역의 정보가 주어졌을 때, 각 교역에 대해 특산품을 무사히 전달할 수 있는지 판정하는 프로그램을 작성하라.
입력#
입력은 다음 형식으로 표준 입력에서 주어진다.
N M K
U1 V1
U2 V2
:
UM VM
S1 S2 … SN
Q
A1 B1
A2 B2
:
AQ BQ- 첫 번째 줄: 도시의 수 N, 도로의 수 M, 주의 수 K
- 다음 M개 줄: 각 도로가 연결하는 두 도시의 번호 Ui, Vi
- 다음 줄: 각 도시가 속한 주의 번호 S1, S2, …, SN
- 다음 줄: 교역 횟수 Q
- 다음 Q개 줄: 각 교역의 출발 도시 Ak와 도착 도시 Bk
출력#
표준 출력에 Q개의 줄로 출력한다. k번째 줄 (1 ≦ k ≦ Q)에는 k번째 교역에서 특산품을 전달할 수 있으면 1을, 불가능하면 0을 출력한다.
🧐 관찰 및 접근#
- 무향 그래프와 정점에 $S_j$값이 주어진다.
- $S_i \in \{S_{A_K}, S_{B_K}\}$의 정점만을 이용해서$A_K, B_K$ 사이를 왕복할 수 있을까?
- 에? 걍 유니온파인드로 묶어서 컴포넌트 하나로 생각하고, 사이에 간선이 있는지 보면 되나?
- 아, 각 $S$에 대해 컴포넌트가 하나가 아닐 수도 있다.
- 케이스를 나눠보자.
- $\text{Case 1:} \, {S_{A_k} = S_{B_k}}$
- 이미 돌린 유파에서 같은 그룹이면 1, 아니면 0이다.
- $Case 2: {S_{A_k} \ne S_{B_k}}$
- $(u, v) \in E, S_u = S_{A_k}, S_v = S_{B_k}$인 간선만 추가하면 되는데…
- $S_A, S_B$집합이 둘다 컴포넌트가 여러개고 지그재그로 들어가면 조금 곤란해진다.
- 근데 생각보다 이 경우의 수가 결국 $M$에 바운드 되니까 쿼리 캐싱만 하면 될거같기도?
- 기준은 $S$임에 주의할것.
- $\text{Case 1:} \, {S_{A_k} = S_{B_k}}$
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> M >> K;
rep(i, 0, M){
int u, v; cin >> u >> v;
u--; v--;
edges.push_back({u, v});
}
rep(i, 0, N) cin >> S[i];
UnionFind UF(N);
for(auto [u, v]: edges) if(S[u] == S[v]) UF.merge(u, v);
for(auto [u, v]: edges) if(S[u] != S[v]){
int pu = UF.find(u);
int pv = UF.find(v);
if(pu > pv) swap(pu, pv);
edges2[{min(S[pu], S[pv]), max(S[pu], S[pv])}].push_back({pu, pv});
}
for(auto &[key, vec] : edges2){
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
}
int Q; cin >> Q;
vector<pair<pii, array<int, 3>>> Query; // {{Su, Sv}, {u, v, idx}}
rep(i, 0, Q){
int u, v; cin >> u >> v;
u--; v--;
u = UF.find(u);
v = UF.find(v);
if(u > v) swap(u, v);
Query.push_back({{min(S[u], S[v]), max(S[u], S[v])}, {u, v, i}});
}
sort(all(Query));
vector<int> ans(Q, 0);
UnionFind UF2(N);
vector<int> used;
rep(q, 0, Q){
if(q > 0 && Query[q].first == Query[q-1].first){
auto [u, v, idx] = Query[q].second;
if(UF2.find(u) == UF2.find(v)) ans[idx] = 1;
continue;
}
for(auto x: used) UF2.par[x] = x;
used.clear();
auto [Su, Sv] = Query[q].first;
for(auto [u, v]: edges2[{Su, Sv}]){
if(UF2.merge(u, v)){
used.push_back(u);
used.push_back(v);
}
}
auto [u, v, idx] = Query[q].second;
if(UF2.find(u) == UF2.find(v)) ans[idx] = 1;
}
rep(i, 0, Q) cout << ans[i] << "\n";
}