#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
int p[300300], p2[300300], sz[300300], nxt[300300];
vector<int> nq[300300];
set<int> k[300300];
set<pair<int, int>> s[300300];
// 1. 컴포넌트 루트 찾기
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
// 2. 경로 탐색용 루트 찾기 (죽은 노드 방지)
int find2(int x) {
x = find(x); // 현재 활성화된 컴포넌트의 루트로 변환
return x == p2[x] ? x : p2[x] = find2(p2[x]);
}
// 3. 그룹 병합 함수 (완벽한 Small-to-Large 최적화 적용)
bool merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return false;
// [핵심] 3개 컨테이너 크기의 총합을 비교하여 한 번에 Swap
if(k[x].size() + s[x].size() + nq[x].size() < k[y].size() + s[y].size() + nq[y].size()) {
swap(k[x], k[y]);
swap(s[x], s[y]);
swap(nq[x], nq[y]);
}
// 그룹 관계는 항상 x가 y를 흡수하도록 유지
p[y] = x;
p2[y] = x; // 경로(p2)도 새 루트로 동기화
sz[x] += sz[y];
// 이제 y가 무조건 더 작은 그룹임이 보장되므로 안심하고 순회
for(const auto &nqv : nq[y]) nq[x].push_back(nqv);
for(const auto &kv : k[y]) {
if(k[x].insert(kv).second) {
auto it = s[x].lower_bound({kv, 0});
while(it != s[x].end() && it->first == kv) {
nq[x].push_back(it->second);
it = s[x].erase(it);
}
}
}
for(const auto &[col, to] : s[y]) {
if(k[x].count(col)) {
nq[x].push_back(to);
} else {
s[x].insert({col, to});
}
}
// 메모리 최적화를 위해 사용이 끝난 y의 데이터 초기화
k[y].clear();
s[y].clear();
nq[y].clear();
return true;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(), m = v.size();
// 그래프 간선 정보 등록
for(int i=0; i<m; i++) {
s[u[i]].insert({c[i], v[i]});
s[v[i]].insert({c[i], u[i]});
}
queue<int> q;
// 초기화
for(int i=0; i<n; i++) {
q.push(i);
p[i] = i;
p2[i] = i;
sz[i] = 1;
nxt[i] = -1;
k[i].insert(r[i]);
auto it = s[i].lower_bound({r[i], 0});
while(it != s[i].end() && it->first == r[i]) {
nq[i].push_back(it->second);
it = s[i].erase(it);
}
}
// 메인 탐색 로직 (Boruvka Style)
while(!q.empty()) {
int u = find(q.front());
q.pop();
if(nxt[u] != -1) continue; // 이미 탈출구가 정해진 그룹은 탐색 패스
while(!nq[u].empty()) {
int x = find(nq[u].back());
nq[u].pop_back();
if(u == x) continue; // 자기 자신(같은 그룹)으로 가는 간선 무시
// 사이클 발견 시 압축 진행
if(find2(x) == u) {
vector<int> L;
int curr = x;
// [핵심] 죽은 노드를 밟지 않고 find()로 살아있는 다음 Root로 O(1) 점프
while(curr != u) {
L.push_back(curr);
curr = find(nxt[curr]);
}
// 수집된 컴포넌트들을 u를 중심으로 모두 병합
for(auto i : L) merge(u, i);
// 병합 후 새롭게 태어난 거대 그룹의 상태 초기화
u = find(u);
nxt[u] = -1;
p2[u] = u; // 새 경로의 끝점임을 명시
q.push(u); // 다시 탐색 큐에 삽입
} else {
// 사이클이 아니면 경로 연장
nxt[u] = x;
p2[u] = x;
}
break;
}
}
// 4. 마지막 정답 도출 시 반드시 find(i)를 사용하여 최종 루트 참조
int mn = 1e9;
for(int i=0; i<n; i++) {
int root = find(i);
if(nxt[root] == -1) mn = min(mn, sz[root]);
}
vector<int> ans(n, 0);
for(int i=0; i<n; i++) {
int root = find(i);
if(nxt[root] == -1 && sz[root] == mn) ans[i] = 1;
}
return ans;
}
