BZOJ 1854: [Scoi2010]游戏 (并查集)
Description
lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？
Input
输入的第一行是一个整数N，表示lxhgww拥有N种装备 接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值
Output
输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。
Sample Input
3 1 2 3 2 4 5
Sample Output
2
HINT
【数据范围】 对于30%的数据，保证N < =1000 对于100%的数据，保证N < =1000000
Source
思路：
看到了二分图匹配的题解，但是感觉很错啊？
正确的做法是，将武器看成边，将每个武器的2种属性看成点。
使用某种属性，就要消耗一条边。
因此如果一个联通快是树形结构，k个点，k-1条边，因此有一个属性无法被使用。
由于要求是从1开始递增得攻击，因此显然使得属性最大的点不被使用是最优的。
如果一个联通块有环，那么所有的树型都可以被使用。
注意这个联通快有无环影响计数的思维，和codeforces # 440 div2 E. Points, Lines and Ready-made Titles 很像
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月25日 星期三 17时00分25秒
4File Name :1854.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=1E6+7;
24const int M=1E4+7;
25int n;
26bool ok[M];
27int f[M];
28
29void init()
30{
31 ms(ok,false);
32 for ( int i = 1 ; i < M ; i++) f[i] = i;
33}
34int root ( int x)
35{
36 if (x!=f[x]) f[x] = root(f[x]);
37 return f[x];
38}
39int main()
40{
41 #ifndef ONLINE_JUDGE
42 freopen("./in.txt","r",stdin);
43 #endif
44
45 cin>>n;
46 init();
47 for ( int i = 1 ; i <= n ; i++)
48 {
49 int x,y;
50 int fx,fy;
51 scanf("%d %d",&x,&y);
52 fx = root(x);
53 fy = root(y);
54 if (fx!=fy)
55 {
56 if (fx<fy) swap(fx,fy);
57 ok[fy] = true;
58 f[fy] = fx;
59 }
60 else ok[fy] = true;
61 }
62 int ans;
63 for ( int i = 1 ; i < M ; i++)
64 if (!ok[i])
65 {
66 ans = i-1;
67 break;
68 }
69
70 cout<<ans<<endl;
71
72 #ifndef ONLINE_JUDGE
73 fclose(stdin);
74 #endif
75 return 0;
76}