裸地并查集

【题目描述】

或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

【输入】

输入由两部分组成。

第一部分以N，M开始。N为问题涉及的人的个数(1≤N≤20000)。这些人的编号为1,2,3,…, N。下面有M行(1≤M≤1000000)，每行有两个数ai,biai,bi，表示已知aiai和bibi是亲戚。

第二部分以Q开始。以下Q行有Q个询问(1≤ Q ≤1000000)，每行为ci,dici,di，表示询问cici和didi是否为亲戚。

【输出】

对于每个询问ci,dici,di，输出一行：若cici和didi为亲戚，则输出“Yes”，否则输出“No”。

【输入样例】

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

【输出样例】

Yes
No
Yes

#include
#include
#include
using namespace std;
const int maxn = 20005;
int father[maxn];
int find(int x)
{return father[x]==x?x:father[x]=find(father[x]);
}
bool check(int a,int b)
{if(a==b)return 1;else return find(a)==find(b);    
}
void unio(int a,int b)
{int c=find(a),d=find(b);if(c!=d)father[c]=d;
}
int main()
{int N,M,Q;cin>>N>>M;for(int i=1;i<=N;i++)father[i]=i;for(int i=1;i<=M;i++){int a,b;scanf("%d%d",&a,&b);if(a!=b)unio(a,b);}cin>>Q;for(int i=1;i<=Q;i++){int a,b;scanf("%d%d",&a,&b);if(check(a,b))printf("Yes\n");else printf("No\n");}
}

【题目描述】

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：

1、我朋友的朋友是我的朋友；

2、我敌人的敌人是我的朋友；

所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

【输入】

第1行为n和m，1

以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。

【输出】

一个整数，表示这n个人最多可能有几个团伙。

【输入样例】

6 4
1 1 4
0 3 5
0 4 6
1 1 2

【输出样例】

3

#include
using namespace std;
const int maxn = 1005;
int f[maxn],e[maxn];
bool vis[maxn];
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);
}
void Union(int u,int v){int f1 = find(u), f2 = find(v);if(f1 != f2)f[f1] = f2;
}
void Sep(int u,int v){Union(e[u], v);
}
int main(){int N,M,cnt = 0;cin>>N>>M;for(int i = 1; i <= N; i++)f[i] = i;for(int i = 1; i <= M; i++){int u, v, p;cin>>p>>u>>v;if(!p)Union(u, v);if(p){if(!e[u])e[u] = v;else Sep(u, v);if(!e[v])e[v] = u;else Sep(v, u);}        }for(int i = 1; i <= N; i++)if(!vis[find(i)])vis[find(i)] = 1, cnt++;cout<<cnt;
}

【题目描述】

Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，…...，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

【输入】

第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。

第2~n+1行，每行ci，di表示i朵云的价钱和价值。

第n+2~n+1+m行，每行ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。

【输出】

一行，表示可以获得的最大价值。

【输入样例】

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

【输出样例】

1

【提示】

【数据范围】

30%的数据保证：n≤100

50%的数据保证：n≤1,000；m≤100；w≤1,000

100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000

#include
#include
#include
#include
using namespace std;
const int maxn = 10005;
int f[maxn],c[maxn],d[maxn],C[maxn],D[maxn],p[maxn];int find (int x)
{return f[x]==x?x:f[x]=find(f[x]);
}
void unin(int a,int b)
{int c=find(a),d=find(b);if(c==d)return ;f[c]=d;
}int main()
{int N,M,W;cin>>N>>M>>W;for(int i=1;i<=N;i++)f[i]=i;for(int i=1;i<=N;i++)scanf("%d%d",&c[i],&d[i]);for(int i=1;i<=M;i++){int a,b;scanf("%d%d",&a,&b);unin(a,b);}for(int i=1;i<=N;i++){int u=find(i);C[u]+=c[i];D[u]+=d[i];}for(int i=1;i<=N;i++){if(!C[i]||!D[i])continue;for    (int j=W;j>=C[i];j--){p[j]=max(p[j],p[j-C[i]]+D[i]);}}cout<endl;return 0;    
}

【题目描述】

现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

【输入】

由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。

【输出】

按照输入的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

【输入样例】

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

【输出样例】

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur
注意：没有找到父亲map返回的是“”，s.substr是截取字串函数

#include
#include
#include

【题目描述】

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

【输入】

第一行：三个整数n，（n≤100,000,m≤200,000），分别表示有n个人，m个信息。

以下m行：信息包含两种形式：

M a b：表示a和b具有亲戚关系。

Q a：要求输出a所在家族的人数。

【输出】

要求输出a所在家族的人数。

【输入样例】

5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4

【输出样例】

1
1
3
1
4

#include
#include
#include
using namespace std;
const int maxn = 100005;
int father[maxn],num[maxn];
int find(int x)
{return father[x]==x?x:father[x]=find(father[x]);
}
int check(int a)
{return num[find(a)];    
}
void unio(int a,int b)
{int c=find(a),d=find(b);if(c!=d){num[d]+=num[c];father[c]=d;}
}
int main()
{int N,M,Q;cin>>N>>M;for(int i=1;i<=N;i++){father[i]=i;num[i]=1;}            for(int i=1;i<=M;i++){string order;                cin>>order;//cout<//cout<<"a";if(order=="M"){int a,b;scanf("%d%d",&a,&b);if(a!=b)unio(a,b);}else if(order=="Q"){int a;scanf("%d",&a);printf("%d\n",(check(a)));}}}

【题目描述】

Alice和Bob玩了一个古老的游戏：首先画一个n × n的点阵（下图n = 3）

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了(n ≤ 200)，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？

【输入】

输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行，每行首先有两个数字(x, y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是"D "，则是向下连一条边，如果是"R "就是向右连一条边。输入数据不会有重复的边且保证正确。

【输出】

输出一行：在第几步的时候结束。假如m步之后也没有结束，则输出一行“draw”。

【输入样例】

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

【输出样例】

4

题解：二维并查集，当两个点在同一集合中，则它们已首尾相连

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 301;
struct node{int x,y;
}f[maxn][maxn];
node find(node a)
{if((f[a.x][a.y].x==a.x)&&(f[a.x][a.y].y==a.y))return f[a.x][a.y];return f[a.x][a.y]=find(f[a.x][a.y]);
}
int main()
{int N,M;cin>>N>>M;for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)f[i][j].x=i,f[i][j].y=j;for(int i=1;i<=M;i++){int x,y;char c;node k1,k2;cin>>x>>y>>c;if(c=='D')k1=find(f[x][y]),k2=find(f[x+1][y]);else k1=find(f[x][y]),k2=find(f[x][y+1]);if((k1.x==k2.x)&&(k1.y==k2.y)){cout<return 0;
　　　　　}f[k1.x][k1.y]=k2;}cout<<"draw"<<endl;
}

转载于:https://www.cnblogs.com/EdSheeran/p/8470154.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！