游戏 | 二分图匹配、并查集

题目大意：
每个装备给出两个属性值，每次只能选择一个

从1的属性值开始选，每个装备只能选择一次，并且只能选择一个属性，问最多选择几个？

题目思路：
一个经典的套路

因为路径已经确定，所以也就硬性要求了这一步该选什么

1 2

3 1

这个样例来说，假设第一件装备选择了1，那么第二件装备就没法选择，但是你会发现可以选择两个。

此时有没有一种方法可以使得1选2，2去选1呢

模拟这个过程，其实就是匈牙利匹配的过程

所以搞一个匈牙利匹配即可

Code:

/*** keep hungry and calm CoolGuang!***/
ll n,m,p;
vector<int>v[maxn];
int vis[maxn],match[maxn];
int dfs(int u){
    for(int e:v[u]){
        if(!vis[e]){
            vis[e] = 1;
            if(!match[e]||dfs(match[e])){
                match[e] = u;
                return 1;
            }
        }
    }return 0;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(i);
        v[y].push_back(i);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(!dfs(i)){
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d\n",n);
    return 0;
}
/**
6 8
1 2 1
1 3 1
3 4 1
2 5 1
4 6 1
5 6 1
2 4 1
***/

Extend:
考虑这种问题有一种并查集的普遍解法？

问题形如2020牛客多校某场的一个题

这个题顺序维护就好了

Code:

/*** keep hungry and calm CoolGuang!***/
ll n,m,p;
int pre[maxn],sz[maxn],edg[maxn],rt[maxn],res[maxn];
int Find(int x){
    return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main()
{
    read(n);
    for(int i=1;i<=10001;i++){
        pre[i] = i;
        sz[i] = 1;
        edg[i] = 0;
    }
    for(int i=1;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);
        int dx = Find(x),dy = Find(y);
        if(dx != dy){
            pre[dy] = dx;
            sz[dx] += sz[dy];
            edg[dx] += edg[dy]+1;
        }else if(dx == dy) edg[dx]++;
    }
    for(int i=1;i<=10001;i++) rt[i] = Find(i);
    for(int i=1;i<=10001;i++){
        int k = i;
        while(k<=10001&&rt[k] == rt[i]) k++;
        k--;
        if(edg[rt[k]]<sz[rt[k]]){
            if(res[rt[k]]+k-i+1<=sz[rt[k]]-1) res[rt[k]] += k-i+1;
            else{
                int diff = sz[rt[k]]-1-res[rt[k]];
                printf("%d\n",i+diff-1);
                return 0;
            }
        }
        i = k;
    }
    return 0;
}
/**
3
1 2
3 1
3 3
***/