并查集
Cube Stacking
题目
Description
Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations: moves and counts.
- In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
- In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value. Write a program that can verify the results of the game.
Input
- Line 1: A single integer, P * Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a ‘M’ for a move operation or a ‘C’ for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X. Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
Output
Print the output from each of the count operations in the same order as the input file. Sample Input 6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4 Sample Output 1 0 2 题目链接POJ-1988-Cube Stacking
解题思路
POJ 的题真的是对小白选手的一个大的磨炼了，看了好久才明白题意，然后发现还是不会写题意就是给你一个数n，然后又n次操作，每次操作有两种情况如果第一个字符是 M 那么就是把含 y 的队伍放在含 x 队伍下面，如果是 C 的话就输出 x 下面有几个数 ** 这个题真的是很妙呀！把递归和并查集完美的结合在一起的，我们需要先设置三个数组分别 用于 1，找该节点的父节点，2该节点到其祖先节点的距离，3以该节点为祖先节点的点有几个；每次查找然后更新一旦遇到C，就用该节点的祖先节点包含的点数减去这个点到其祖先节点的数量就可以啦，但是如何实施就是很关键有点点困难了！不过递归加回溯却刚好可以解决这个问题**真的太舒服了，这个操作真是6呀！
代码
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int fa[30500];// 存节点
int a[30500];// 以该节点为父节点的节点一共有几个
int b[30200];// 该节点到其父节点的距离
int find(int x)
{// 整个程序的核心算法 递归用的真是666666
if(fa[x]!=x)
{
int s=fa[x];// 将其上一个节点的值付给s
fa[x]=find(fa[x]);
a[x]+=a[s];//x到其祖先节点的值等于他到他父节点的值加
//上起父节点到其祖先节点的距离
}
return fa[x];
}
void jion(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
fa[yy]=xx;
a[yy]+=b[xx];//因为把yy的父节点接到xx的父节点后面了
b[xx]+=b[yy];//所以yy到最终祖先节点的距离等于他到本来的祖先的距离
} //加上xx到其祖先节点的距离，此时新的祖先节点的子孙
} //数量等于 以前 xx 的子孙加上 yy 的祖孙；
int main()
{
int n,x,y;
char c;
while(~scanf("%d",&n))
{
for(int i=1;i<=30009;i++)
{
a[i]=0;//自己到自己的距离为0；
b[i]=1;//刚开始的时候每个节点都是一个祖先节点包含自己所以为1；
fa[i]=i;//第i个值为自己方便以后找祖先节点
}
while(n--)
{
scanf(" %c",&c);
if(c=='M')
{
scanf("%d%d",&x,&y);
jion(x,y);
}
else {
scanf("%d",&x);
int s=find(x);//查找 x的祖先节点
printf("%d\n",b[s]-a[x]-1);
}// x 下面的节点等于总结点数减去x到祖先节点的个数
}
}
return 0;
}HDU - 3635- Dragon Balls
题目
Five hundred years later, the number of dragon balls will increase unexpectedly, so it’s too difficult for Monkey King(WuKong) to gather all of the dragon balls together.
His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities’ dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls. Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far. Input The first line of the input is a single positive integer T(0 < T <= 100). For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000). Each of the following Q lines contains either a fact or a question as the follow format: T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different. Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N) Output For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space. Sample Input 2 3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1 Sample Output Case 1: 2 3 0 Case 2: 2 2 1 3 3 2 题目传送门：HDU - 3635- Dragon Balls
解题思路
题目大意： 先给一个数 t 表示有 t 组测试 然后 每组数据有两个数 n，m 分别表示一共有n个数，m次操作，T x，y 表示把含x的队伍移动到含y的队伍里面，Q x表示查询x然后需要输出x现在的祖先节点是谁，这个节点一共有几个成员，x被移动了几次；另外每组开始的时候需要输出Case x:（这是第几组测试）
解题思路
这个题真的是麻烦，还是带权并查集，记录祖先节点好办每次查找就行了，总共个数也好办开个数组就行了，每次记录该祖先节点的总结点数，一单合并只要祖先节点相加就可以了，就是移动的次数难受的一批，我刚开始直接开个数组存，但是发现不行如果1,2,4；现在移动的是2，那么只用2以上的节点的移动次数加一了，1就没变所以说还是需要改进。。。经过我不懈的思考查找CSDN终于发现了一个秒方法，就是每次改变值把祖先节点的移动次数加一就行，然后查找节点的时候在回溯的工程中一个个的都加上，真实妙呀！！！
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int fa[20000],sum[20000];
int ch[20000];
int find(int x)
{
if(x!=fa[x])
{
int s=fa[x];
fa[x]=find(s);
ch[x]+=ch[s];//回溯的时候更新变化数
}
return fa[x];
}
void join(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
sum[yy]+=sum[xx];//总结点数相加
fa[xx]=yy;
ch[xx]++;//后面的主节点变化数+1；
}
}
int main()
{
int t,xx,y,n,m;
char c;
scanf("%d",&t);
int k=1;
while(t--)
{
int flag=1;
scanf("%d%d",&n,&m);
printf("Case %d:\n",k++);
for(int i=1;i<=n;i++)
{
sum[i]=1;
ch[i]=0;
fa[i]=i;
}
while(m--)
{
scanf(" %c",&c);
if(c=='T')
{
scanf("%d%d",&xx,&y);
join(xx,y);
}
else{
scanf("%d",&xx);
int xxx=find(xx);
printf("%d %d %d\n",xxx,sum[xxx],ch[xx]);
}
}
}
return 0;
}HDU - 3047-Zjnu Stadium
题目
In 12th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1–300, counted clockwise, we assume the number of rows were infinite. These days, Busoniya want to hold a large-scale theatrical performance in this stadium. There will be N people go there numbered 1–N. Busoniya has Reserved several seats. To make it funny, he makes M requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A. For example: A is in column 4th and X is 2, then B must in column 6th (6=4+2). Now your task is to judge weather the request is correct or not. The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct. Please find out all the incorrect requests and count them as R. Input There are many test cases: For every case: The first line has two integer N(1<=N<=50,000), M(0<=M<=100,000),separated by a space. Then M lines follow, each line has 3 integer A(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B), separated by a space.
Output For every case: Output R, represents the number of incorrect request. Sample Input 10 10 1 2 150 3 4 200 1 5 270 2 6 200 6 5 80 4 7 150 8 9 100 4 8 50 1 7 100 9 2 100 Sample Output 2 Hint: （PS： the 5th and 10th requests are incorrect）
解题思路
题目大意 就是在一个圆形的桌子上坐着，现在给你n，m两个数分别表示n个人m组数据，每组数据包含x，y，s，分别表示x距离y为s，然后让你判断有几个数据是不合法的 解题思路 emmm mmp呀！你吃个饭那来这么多事呀？小明附体？？？这个题意识属于带权并查集，构图之类的都很容易但是如何确定关系呢？我怎么确定这两个点冲突了呢？emmmm这是这个题的关键步骤，其实我们可以开一个数组表示它距离自己的祖先节点的距离，以为一个队伍的节点只有一个祖先节点，所以以祖先节点为原点，这样的话不是一对的肯定不会冲突，冲突的话肯定是一队的而且位置一样，或者这两个节点的距离和上次的不一样那么就是不合格的，确定好思路了，那么我们就看代码吧
代码
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int fa[50500];
int sum[50500];//表示到节点的距离
const int mod=300;//圆形坐着一旦距离大于300就是又一圈开始了
int find(int x)
{
if(x!=fa[x])
{
int s=fa[x];
fa[x]=find(s);
sum[x]=(sum[s]+sum[x])%mod;//因为可能出现相减为负值的情况
} //每次更新到祖先节点的距离
return fa[x];
}
bool join(int x,int y,int s)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
fa[yy]=xx;
sum[yy]=(sum[x]-sum[y]+s+mod)%mod;//两个祖先节点不等就更新 新的祖先节点的位置
} // 这个表示的是y的祖先节点更新后距离xx的距离
else{ // 比如说1-2是40；3-4是20；那么现在有了1-3为10；把这三个节点连一起后
if(sum[y]!=(sum[x]+s)%mod) return true;// 4-2的距离就是40-20+10=30；
}// 说明两个节点的公共祖先是相同的，如果现在的距离和以前的不一样了，那说明也是不行的
return 0;
}
int main()
{
int n,m,x,y,s;
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
sum[i]=0;
}
int ans=0;
while(m--)
{
scanf("%d%d%d",&x,&y,&s);
if(join(x,y,s))
ans++;
}
printf("%d\n",ans);
}
return 0;
}