题目链接：https://ac.nowcoder.com/acm/problem/20566
题目大意：
每个装备给出两个属性值，每次只能选择一个
从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
***/