📝 문제 정보#
문제 번역#
Bessie는 수학 지식을 향상시키기 위해 그래프 이론 강좌를 수강하고 있는데, 다음 문제에서 막혔습니다. 그녀를 도와주세요!
연결된 무방향 그래프가 주어집니다. 정점은 $1\dots N$으로, 간선은 $1\dots M$으로 라벨링되어 있습니다 ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$).
그래프의 각 정점 $v$에 대해 다음 과정을 수행합니다:
- $S=\{v\}$, $h=0$으로 설정합니다.
- $|S|
- 정확히 한쪽 끝점만 $S$에 속한 모든 간선 중에서, 라벨이 가장 작은 간선을 $e$라고 합니다.
- $S$에 속하지 않은 $e$의 끝점을 $S$에 추가합니다.
- $h=10h+e$로 설정합니다.
이 과정의 모든 반환값을 구하세요.
입력#
첫 번째 줄에 $N$과 $M$이 주어집니다.
다음 $M$개의 줄에는 $e$번째 간선의 양 끝점 $(a_e,b_e)$가 주어집니다 ($1\le a_e 이 간선들이 연결된 그래프를 형성하며, 각 정점 쌍을 연결하는 간선은 최대 1개임이 보장됩니다. $N$개의 줄을 출력합니다. $i$번째 줄에는 정점 $i$에서 시작하는 과정의 반환값을 출력합니다.출력#
🧐 관찰 및 접근#
💻 풀이#
void solve(){
cin >> N >> M;
UnionFind UF(N+1), UF_head(N+1), UF_tail(N+1);
rep(i, 0, M){
int a, b; cin >> a >> b;
if(UF.merge(a, b)){
edges.push_back({a, b, i+1});
int a_tail = UF_tail.find(a);
int b_head = UF_head.find(b);
nxt[a_tail] = b_head;
UF_head.merge(a, b);
UF_tail.merge(b, a);
}
}
vector<int> order;
rep(i, 1, N+1) if(UF_head.find(i) == i){
int cur = i;
while(cur != 0){
order.push_back(cur);
cur = nxt[cur];
}
}
vector<int> to_idx(N+1, -1);
rep(i, 0, N) to_idx[order[i]] = i;
// for(auto x: order) cout << x << " "; cout << "\n";
UF_head.init(N+1);
UF_tail.init(N+1);
LazySegmentTree LST(N);
mint m10 = 10;
for(auto [a, b, w]: edges){
int LH = UF_head.find(a), LT = UF_tail.find(a);
int RH = UF_head.find(b), RT = UF_tail.find(b);
LH = to_idx[LH];
LT = to_idx[LT];
RH = to_idx[RH];
RT = to_idx[RT];
// cout << LH << " " << LT << " " << RH << " " << RT << "\n";
mint Lval = LST.query(to_idx[a], to_idx[a]), Rval = LST.query(to_idx[b], to_idx[b]);
LST.update(LH, RT, {10, w});
LST.update(LH, LT, {m10.pow(UF_head.cnt[UF_head.find(b)]-1), Rval});
LST.update(RH, RT, {m10.pow(UF_tail.cnt[UF_tail.find(a)]-1), Lval});
UF_head.merge(a, b);
UF_tail.merge(b, a);
}
rep(i, 1, N+1) cout << LST.query(to_idx[i], to_idx[i]) << "\n";
}