并查集
一个基础的并查集问题，n个人，每个人只能有一个信仰，每次给出两个人相同信仰的编号(编号从1到n),一共m次，问一共有多少种信仰。
#include <iostream>
typedef long long ll;
const ll N = 5e4+7;
using namespace std;
ll fa[N];
int n, m;
void init(){
for (int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x){ //查找
return x == fa[x] ? x : fa[x]=find(fa[x]);
}
void mergeset(int x, int y){//合并
fa[find(x)]=find(y);
}
int main()
{
int cnt=1;
while (cin >> n >> m)
{
if(n == 0 && m==0) break;
init();
for (int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
mergeset(x , y);
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (fa[i] == i)
ans++;
}
cout<<"Case "<<cnt++<<": "<<ans<<endl;
}
return 0;
}查找与0同一组的数目
#include <iostream>
typedef long long ll;
const ll N = 3e4 + 7;
using namespace std;
ll fa[N];
int n, m;
void init()
{
for (int i = 0; i <= n - 1; i++)
fa[i] = i;
}
int find(int x)
{ //查找
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mergeset(int x, int y)
{ //合并
x=find(x),y=find(y);
if(x==0) fa[y]=0;
else fa[x]=y;
}
int main()
{
int cnt = 1;
while (cin >> n >> m)
{
int x,y,k;
if (n == 0 && m == 0)
break;
init();
while (m--)
{
cin>>k;
cin >> x;
for (int i = 2; i <= k; i++)
{
cin >> y;
mergeset(x, y);
x = y;
}
}
ll ans = 0;
for (int i = 0; i <= n-1; i++)
{
if (find(i) == 0)
ans++;
}
cout <<ans<< endl;
}
return 0;
} 题意：给你n个人，这n个人只属于两个不同的团体，m次操作
A x y:询问x,y是否是在一个团体
D x y:x,y不是一个团体
解法：一共有n个人，x,y不是一个团体，可以看成x与y的对立面是一个团体的，因此可以用一个2n的数组来存这个关系，接下来就是普通的并查集即可。
#include <iostream>
#include<cstdio>
typedef long long ll;
const ll N = 1e5 + 7;
using namespace std;
ll fa[N << 1];
int n, m;
void init()
{
for (int i = 1; i <= n * 2; i++)
fa[i] = i;
}
int find(int x)
{ //查找
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mergeset(int x, int y)
{ //合并
fa[find(x)] = find(y);
}
int main()
{
int cnt = 1;
int t;
cin>>t;
while (t--){
scanf("%d%d",&n,&m);
int x, y;
char op;
init();
for (int i = 1; i <= m; i++){
scanf(" %c%d%d",&op,&x,&y);
if(op=='D'){
mergeset(x,y+n);
mergeset(x+n,y);
}
else{
if(find(x) == find(y+n)){
printf("In different gangs.\n");
}
else if(find(x) == find(y)){
printf("In the same gang.\n");
}
else printf("Not sure yet.\n");
}
}
}
return 0;
} 题意：
给你n个人，以及他们之间的联系。已知1号的精力，1号要去和其他人员交易，交易要花费精力，同时会获得收益，让你求怎么样才能获得最大收益。
题解：
其实这道题就是一个背包加并查集，先用并查集求出他们之间的关系，然后直接背包就行了，记得在dp的时候判断他们之间是否有关系，有关系才能装进去。
#include <bits/stdc++.h>
typedef long long ll;
const ll N = 1e5 + 7;
using namespace std;
ll fa[N],dp[N],a[N],b[N];
int n, m,k;
void init()
{
for (int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x)
{ //查找
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mergeset(int x, int y)
{ //合并
fa[find(x)] = find(y);
}
int main()
{
int t;
cin >> t;
while (t--)
{
scanf("%d%d%d", &n, &m, &k);
int x, y;
init();
for(int i = 2; i <= n;i++){
cin>>a[i]>>b[i];
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
mergeset(x, y);
}
memset(dp,0,sizeof(dp));
for(int i=2;i<=n;i++){
for(int j=k;j>=a[i];j--){
if(find(i) == find(1)){
dp[j] = max(dp[j] , dp[j-a[i]]+b[i]);
}
}
}
cout<<dp[k]<<endl;
}
return 0;
}
查看20道真题和解析