GYM 100685 G【并查集】

2024-08-24 11:38

文章标签 查集 gym 100685

本文主要是介绍GYM 100685 G【并查集】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一开始看题就水了一发bitset，本地是没有什么问题，但是交上去果断地MLE了。

那么就想到乱搞，假设将其变成一颗有根树，如果dfs的时候走的是正的边，就在正的并查集里面merge，如果走的是负的边，就在反的并查集里面merge。

对于一个查询，查询一下他们的LCA，如果他们的LCA，在u（或者v）正的并查集中，在另一个反的并查集内，那么就是可以访问，否则不行。

大家可以脑补一下图像，必然是这样的。

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 100005using namespace std;int fa1[MAXN],fa2[MAXN];int n,m;
int depth[MAXN];int Index;
int head[MAXN],nxt[2*MAXN],node[2*MAXN];int from[MAXN],to[MAXN];int p[MAXN][20];
int deep[MAXN];void init()
{Index = 0;memset(head,0,sizeof(head));memset(nxt,0,sizeof(nxt));deep[1] = 0;p[1][0] = 1;for(int i=1;i<=n;i++){fa1[i] = i;fa2[i] = i;}
}void addedge(int u,int v)
{Index++;nxt[Index] = head[u];node[Index] = v;head[u] = Index;
}void dfs(int ret,int fa=-1)
{for(int j=1;j<20;j++)p[ret][j] = p[p[ret][j-1]][j-1];for(int o=head[ret];o;o=nxt[o])if(node[o] != fa){p[node[o]][0] = ret;deep[node[o]] = deep[ret] + 1;dfs(node[o],ret);}
}int getLca(int u,int v)
{if(deep[u] > deep[v])swap(u,v);for(int delta = deep[v]-deep[u],i=0;delta!=0;delta>>=1,++i)if(delta & 1) v = p[v][i];if(u == v) return u;for(int i=19;i>=0;i--){if(p[u][i] == p[v][i]) continue;u = p[u][i],v = p[v][i];}return p[u][0];
}int getfather1(int x)
{if(fa1[x] == x) return x;else return fa1[x] = getfather1(fa1[x]);
}int getfather2(int x)
{if(fa2[x] == x) return x;else return fa2[x] = getfather2(fa2[x]);
}int main()
{scanf("%d",&n);init();for(int i=1;i<n;i++){scanf("%d%d",&from[i],&to[i]);addedge(from[i],to[i]);addedge(to[i],from[i]);}dfs(1);for(int i=1;i<n;i++){if(deep[from[i]] > deep[to[i]]) fa1[getfather1(from[i])] = getfather1(to[i]);else fa2[getfather2(from[i])] = getfather2(to[i]);}scanf("%d",&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);int shit = getLca(x,y);//cout<<shit<<endl;if(getfather1(x) == getfather1(shit) && getfather2(y) == getfather2(shit)) printf("Yes\n");else printf("No\n");}return 0;
}