首页 > 其他分享 >hdu 3635(并查集+路径压缩变形)

hdu 3635(并查集+路径压缩变形)

时间:2023-05-29 22:37:44浏览次数:40  
标签:hdu 3635 int 查集 好久 MAXN 编号 include


解题思路:这道题想了我好久,因为我把城市的编号一起考虑进去了,结果想了好久都没A,最后看了别人的题解居然都没有考虑到城市的编号,不考虑城市编号的问题的话就是一个很水的并查集了。



#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=10000+10;
int parent[MAXN];
int _count[MAXN];
int Rank[MAXN];
int n,m;

void Initiate()
{
    for(int i=1;i<=n;i++)
	{
        parent[i]=i;
        _count[i]=0;
        Rank[i]=1;
    }
}

int Find(int x)
{
    if(x==parent[x]) return x;
    else 
	{
        int tmp=parent[x];
        parent[x]=Find(parent[x]);
        _count[x]+=_count[tmp];//更新转移次数
    }
    return parent[x];
}


void Union(int R1,int R2)
{
    int r1=Find(R1);
    int r2=Find(R2);
    if(r1==r2)return ;
    else 
	{
        parent[r1]=r2;
        _count[r1]++;
        Rank[r2]+=Rank[r1];
        Rank[r1]=0;
    }
}


int main()
{
    int _case,t=1;
    scanf("%d",&_case);
    while(_case--)
	{
        scanf("%d%d",&n,&m);
        Initiate();
        printf("Case %d:\n",t++);
        for(int i=1;i<=m;i++)
		{
            char str[11];
            scanf("%s",str);
            if(str[0]=='T')
			{
                int u,v;
                scanf("%d%d",&u,&v);
                Union(u,v);
            }
			else if(str[0]=='Q')
			{
                int x;
                scanf("%d",&x);
                int y=Find(x);
                printf("%d %d %d\n",y,Rank[y],_count[x]);
            }
        }
    }
    return 0;
}




标签:hdu,3635,int,查集,好久,MAXN,编号,include
From: https://blog.51cto.com/u_16143128/6374305

相关文章

  • hdu 2874(LCA + 节点间距离)
    解题思路:Tarjan离线处理一篇介绍LCA的很好的博客:http://www.cppblog.com/menjitianya/archive/2015/12/10/212447.html#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=10005;structEdge{ intk,next,cost;}edge[maxn&......
  • hdu 4027(线段树)
    题意:给定100000个数,两种操作,0ij表示将ij这段的数字都开根号(向下取整),1ij表示查询ij之间的所有值的和。。。(所有的和都不超过64位)解题思路:这题要做区间的开平方操作,2^64最多可以做8次开平方操作,所以对于每个节点最多只有8次操作,这道题如果lazy思想的话就要保存每个区间被开平方......
  • hdu 3564(线段树+LIS)
    题意:给出1~n的插入顺序,要求每次插入之后的LIS解题思路:这道题确实挺难想的,我最开始想用树状数组每插入一个数就更新一次,如果这么想,那么你就输了。它这里的想法是先将1-n的最终位置都保存起来,然后再一个个去找LIS。这里有点离线算法的意思,至少了解到更新时可以先别急着处理。还有这里......
  • hdu 3874(树状数组+离线算法)
    解题思路:这道题和之前的题一样,查找[l,r]区间内不重复数字的和。可以利用离线算法,实际上离线算法为了解决在查找时出现的矛盾,因为每次询问的区间大小不同,如果单独处理的话可能会对之后的查询有影响,所以离线算法帮助我们把要查询的区间先按照右端点进行排序,因为在处理更靠右的区间时,......
  • poj 1988(并查集)
    题意:进行m次操作,M x y 将包含x的集合移动到y上面,C x, 计算x下面有几个元素。解题思路:这道题很容易想到用并查集,但是这里有点绕;最开始我想到的是建立一个num[x],表示x以下的节点数,但这样会有一个问题,要更新num[x]时,必须要枚举哪些节点的父节点为p,由于节点数太多,所以TLE是难免的......
  • hdu 4101(bfs+博弈)
    题意:题目的意思就是说两个人轮流玩游戏,给你一张地图,这个地图中间有一点-1代表宝藏,AliandBaba轮流走路,如果某一个人能够直接走到宝藏的话,那么他就赢了。地图上其它的点0代表空地,数字代表当前地点的石子当某一人拿石子的时候,他只能拿走一颗。问你谁最后能拿到宝藏;解题思路:宝藏位于-......
  • hdu 1510
    WhiteRectanglesTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)ProblemDescriptionYouaregivenachessboardmadeupofNsquaresbyNsquareswithequalsize.Someofthesquaresarecoloredblack,andthe......
  • hdu 2821
    题意:n*m的格子上有一些方块放在某些格子上,一个格子可能有几个方块,用'a'-'z'来表示方块数量。初始的时候可以选择任意空地作为Pusher初始点,Pusher选择一个方向,然后向这个方向前进直到遇到有方块的格子,Pusher把这个格子的方块清除一个,并把它向前推一格(向前不能出界),如果前面一格有方......
  • hdu 1534(差分约束)
    题意:安排计划,有4种约束方式,给出你这些时间的n个约束..如果计划是可行的,求出每一件事发生的最早时间..否则输出“impossible”..①.FAFaba要在b完成后完成..②.FASaba要在b开始前完成..③.SASaba要在b开始前开始..④.SAFaba要在b结束前开......
  • hdu 1532(最大流)
    解题思路:这是一道典型的模板题,直接套用EK算法即可。。。我感觉最大流的本质就是能否找到一个从源点到汇点的增广路径,并将其最小的边作为增加值,沿着增广路上的边进行更新。AC:#include<iostream>#include<cstdio>#include<cstring>#include<queue>usingnamespacestd;consti......