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

Day1

思路：

看到了二分图匹配的题解，但是感觉很错啊？

正确的做法是，将武器看成边，将每个武器的2种属性看成点。

使用某种属性，就要消耗一条边。

因此如果一个联通快是树形结构，k个点，k-1条边，因此有一个属性无法被使用。

由于要求是从1开始递增得攻击，因此显然使得属性最大的点不被使用是最优的。

如果一个联通块有环，那么所有的树型都可以被使用。

注意这个联通快有无环影响计数的思维，和codeforces # 440 div2 E. Points, Lines and Ready-made Titles  很像

/* ***********************************************
Author :111qqz
Created Time :2017年10月25日 星期三 17时00分25秒
File Name :1854.cpp
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E6+7;
const int M=1E4+7;
int n;
bool ok[M];
int f[M];

void init()
{
    ms(ok,false);
    for ( int i = 1 ; i < M ; i++) f[i] =  i;
}
int root ( int x)
{
    if (x!=f[x]) f[x] = root(f[x]);
    return f[x];
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
  #endif

    cin>>n;
    init();
    for ( int i = 1 ; i <= n ; i++)
    {
        int x,y;
        int fx,fy;
        scanf("%d %d",&x,&y);
        fx = root(x);
        fy = root(y);
        if (fx!=fy)
        {
        if (fx<fy) swap(fx,fy);
        ok[fy] = true;
        f[fy] = fx;
        }
        else ok[fy] = true;
    }
    int ans;
    for ( int i = 1 ; i < M ; i++)
        if (!ok[i]) 
        {
        ans = i-1;
        break;
        }

    cout<<ans<<endl;

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}