唐山网站建设方案咨询,苏州关键词优化怎样,代做毕设网站可信么,盐城网站平台建设带权并查集就是除了维护一个fa数组以外#xff0c;维护一个rank数组#xff0c;有两层含义#xff0c;一个是路径压缩时边的权值#xff0c;#xff0c;再一个是当前点与根节点的相对关系。这个题很明显考察的是 根节点与当前节点的一种相对关系#xff0c;让rank【x】 …带权并查集就是除了维护一个fa数组以外维护一个rank数组有两层含义一个是路径压缩时边的权值再一个是当前点与根节点的相对关系。这个题很明显考察的是 根节点与当前节点的一种相对关系让rank【x】 0 12表示ABC三个种类的动物在刚开始的时候所有的动物的rank值都是0表示还没有给他们安排关系随 着语句的输入1xy表示把x,y置为相同值2xy表示rank【x】 1 rank【y】然而在这里并不是直接改变y的rank的值而是改变y所在的根结点的rank值因为一旦x,y确 立了关系和y在一个集合内的动物都与x建立了关系这样只有改变根节点的rank才能保证每一个动物的rank都会被更新到因为在x所在的集合和y所在的集合没有建立关系 之前x,y的关系可以是任意的。 如果输入1xy首先看x,y是否在一个集合内如果是那麽x,y之间是一种绝对的关系可以通过rank【x】和rank【y】的大小来判断语句的正确性如果不是那麽x,y之间就没有 确定的关系那么这句话就是对的修改rank【y】所在集合的根结点的rank值 输入2xy时和输入1xy时同理。 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includevector
#includemap
#define N 100005
#define lc rt1
#define rc rt1|1
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn 5e4 10;int n,k;
int d,x,y;
int fa[maxn];
int rank[maxn];int find(int x)
{if(fa[x] x)return x;int p find(fa[x]);rank[x] (rank[fa[x]] rank[x])%3;return fa[x] p;
}int main()
{//freopen(in,r,stdin);int cnt 0;scanf(%d%d,n,k);for(int i 0; i n; i) fa[i] i;memset(rank,0,sizeof(rank));for(int i 0; i k; i){scanf(%d%d%d,d,x,y);if(x n||y n||(d 2x y)) {cnt;continue;}int s1 find(x),s2 find(y);//求根节点if(d 1){if(s1 s2){if(rank[x] ! rank[y]) cnt;}else {rank[s2] (rank[x] - rank[y] 3)%3;//更新y的根结点注意不要写错s2fa[s2] s1;//建立x集合与y集合的关系}}else if(d 2){if(s1 s2) {if((rank[x] 1)%3 ! rank[y]) cnt;}else {rank[s2] (rank[x] 1 - rank[y] 3)%3;//同上fa[s2] s1;}}//printf(%d %d\n,i,cnt);}printf(%d\n,cnt);
} 转载于:https://www.cnblogs.com/Norlan/p/4888413.html
