[SCOI2010]游戏

题目链接：https://ac.nowcoder.com/acm/problem/20566?&headNav=acm
题意：给n个装备，每个装备有两个属性，并且最多只能使用一次。求由这些点的属性能最大匹配到的值。

思路：把每个属性看成点，每个装备看成边。然后连接成k个连通块，如果该连通块为树状，则答案只能是k-1；如果连通块为环状，则答案为k。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+5;
const int MOD=1e8+7;

int vis[MAXN];      //记录是否能达到
int fa[MAXN];       //记录父节点
int n;              
int fun(int x)
{
    return fa[x]==x ? x : fa[x]=fun(fa[x]);
}

void unite(int x,int y)
{
    int a=fun(x);
    int b=fun(y);
    if(a==b) {
        vis[a]=1;
        return ;
    }
    if(a>b) swap(a,b);      //看见有大佬的交换写法有：x^=y^=x^=y;  将a为小，b为大
    vis[a]=1;               
    fa[a]=b;                //将小点的父节点为大点
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=1000000;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        unite(a,b);
    }
    for(int i=1;i<=n;i++)
    {

        if(!vis[i]) {
            printf("%d\n",i-1);
            break;
        }

        if(i==n&&vis[i])
        {

            printf("%d\n",i);
        }
    }
    return 0;
}