题意
给一张(n)个点(m)条边的无向图，有一个对于这个无向图的操作，即去除图中的一个生成森林（即所有连通块中生成树的集合）。不断对该无向图进行操作直到该图中的边全部被删除。对于每一条边，输出他是在第几次被删除的。
如果有多种方案，输出其中一种即可
解法
首先我们有一个很好想的(O(MN))暴力
遍历每一条边，每次进行生成树操作：具体来说，就是每次开一个并查集，如果该边的两个端点不在同一个连通块中，则把它们联通，并且把该边从边集中删除；否则跳过该边
考虑我们如何对暴力算法进行优化
如果我们开若干个并查集，每次对于一条边，如果在(1)号并查集中它的两端所连接的点在一个连通块内，我们就在(2)号并查集中进行插入，以此类推...
通过上述算法，我们可以求出每一次操作后形成的生成森林
但是我们会发现，这个算法和原来相比，不仅时间复杂度没有改观，空间复杂度反而变得更劣了
但是这个算法的思想却有一定的启发性
我们可以发现一个性质：对于一条边，如果它可以在第(i)号并查集中插入，那么它也一定可以在(i+1...n)号并查集中插入
这个可以用反证法证明，也可以意会理解一下
发现了这个性质以后，我们就可以二分出第一个可以插入的并查集编号了
这样时间复杂度由(O(MN))优化到了(O(MlogM))
但是空间复杂度仍然无法承受。此时我们可以用哈希表优化空间
我们把若干个并查集排在一起，可以看做一个若干行(n)列的矩阵，把每个矩阵的坐标((x,y))映射成某个数
如果我们把这个矩阵代表的位置全部开出来，需要(M^2)的空间
但实际上我们只有(M)条边，这个矩阵中有许多的空间是闲置的。考虑到每一条边会且仅会插入一个并查集，所以至多会有(2M)个不同的位置，并查集开(2M)的空间即可
将这个数插入哈希表，重新离散化即可
还有一个骚操作：用指针动态开点？？！但是不太会用指针，就先咕着吧
代码
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
int read();
const int N = 2e6 + 10;
const int mod = 1048575;
int n, m, cnt;
struct UnionSet {
int id[N << 1];
void config() {
for (int i = 1; i <= (m << 1); ++i) id[i] = i;
}
int get(int x) {
return x == id[x] ? x : id[x] = get(id[x]);
}
int merge(int x, int y) {
x = get(x), y = get(y);
return (x == y) ? 0 : (id[y] = x);
}
} ufs;
struct HashMap {
int cap;
int head[N], nxt[N];
long long to[N];
void config() {
cap = 0;
memset(head, 0, sizeof head);
}
int insert(long long x) {
int u = x & mod;
to[++cap] = x, nxt[cap] = head[u], head[u] = cap;
return cap;
}
int find(long long x) {
int u = x & mod;
for (int i = head[u]; i; i = nxt[i])
if (to[i] == x) return i;
return 0;
}
} mp;
inline long long gain(int x, int y) {
return 1LL * (x - 1) * n + y;
}
int check(int x, int u, int v) {
int idu = mp.find((gain(x, u))), idv = mp.find(gain(x, v));
if (!idu || !idv || (ufs.get(idu) ^ ufs.get(idv))) return 1;
return 0;
}
int search(int l, int r, int u, int v) {
int res = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid, u, v)) res = mid, r = mid - 1;
else l = mid + 1;
}
return res;
}
int main() {
n = read(), m = read();
ufs.config();
int u, v;
for (int i = 1; i <= m; ++i) {
u = read(), v = read();
int can = search(1, cnt, u, v);
if (!can) {
can = ++cnt;
ufs.merge(mp.insert(gain(cnt, u)), mp.insert(gain(cnt, v)));
} else {
long long x = gain(can, u), y = gain(can, v);
int idu = mp.find(x);
int idv = mp.find(y);
if (!idu) idu = mp.insert(x);
if (!idv) idv = mp.insert(y);
ufs.merge(idu, idv);
}
printf("%d
", can);
}
return 0;
}
int read() {
int x = 0, c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
return x;
}