9
Count connected component after range edge queries.
source link: https://codeforces.com/blog/entry/119245
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Given an empty graph of n vertices and q queries.
Each queries is in the form of (x, y, l) which means you add edges (x + i, y + i) for 0 <= i <= l — 1
Report the number of connected components after q queries.
If I'm not mistaken, I remember there's a trick involving creating log2(n) DSU but I can't make out the details.
Can someone help? Thanks.
N <= 1e5
Q <= 1e5
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK