传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1854
没想到怎么做真是不应该，看到每个武器都有两个属性，应该要想到连边构图的！太不应该了！
构图之后，显然，一个有n个点的联通块要么有n - 1条边，要么有>=n条边（因为可能有重边）。由于一把武器只能使用一次，也就是说一条边只能“属于”其连接的两个点的其中一个。当有n - 1条边时，这时一棵树，这棵树里的边可以满足任意的n - 1个点，因为随便找一个点拉成有根树，使每一条边都“属于”其儿子节点就行了。那么这种情况是不是真的要“随便找一个点”呢？实则不然。因为题目要求了，要按照顺序打boss，所以应该尽量让编号更小的点得到一条边，所以应该让编号最大的点成为树根，对应程序里，在并查集union操作时，应该让编号较小的成为编号较大的儿子，然后标记编号较小的节点。当有>= n条边时，很显然所有点都可以得到一条边，岂不美哉？对应程序里，此时getfa找到的两个fa是一样的，那么就标记这个fa。
#include <cstdio> const int maxn = 1000005; int n, u, v, fu, fv, fa[10005], tem;
char ch, ok[10005]; int getfa(int aa) {
return aa == fa[aa]? aa: fa[aa] = getfa(fa[aa]);
}
inline void readint(int & rt) {
while ((ch = getchar()) < 48);
rt = ch - 48;
while ((ch = getchar()) > 47) {
rt = rt * 10 + ch - 48;
}
} int main(void) {
//freopen("in.txt", "r", stdin);
readint(n);
for (int i = 1; i < 10001; ++i) {
fa[i] = i;
}
for (int i = 0; i < n; ++i) {
readint(u);
readint(v);
fu = getfa(u);
fv = getfa(v);
if (fu == fv) {
ok[fu] = 1;
}
else {
if (fu < fv) {
tem = fu;
fu = fv;
fv = tem;
}
fa[fv] = fu;
ok[fv] = 1;
}
}
int i;
for (i = 1; ok[i]; ++i);
printf("%d\n", i - 1);
return 0;
}