刷了好多题，来贴点题解嘻嘻嘻
普通并查集
Kruskal最小生成树
逆向并查集
带权并查集
- Poj1182_食物链, Poj2492_A Bug's Life
- Poj1984_Navigation Nightmare
- Poj1988_Cube Stacking, HDU3635_Dragon Balls
- Poj1733_Parity game, HDU3038_How Many Answers Are Wrong
牛客网_任意点
#include<bits/stdc++.h>
using namespace std;
int fa[2010], x[110], y[110], rem[1010];
void Init(){
for(int i = 1; i <= 2000; i++) fa[i] = i;
}
int Find(int t){
if(t != fa[t]) fa[t] = Find(fa[t]);
return fa[t];
}
int main(){
int n, ans = 0;
cin >> n;
Init();
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i];
y[i] += 1000;
int fx = Find(x[i]), fy = Find(y[i]);
fa[fy] = fx;
}
for(int i = 0; i < n; i++){
int fx = Find(x[i]);
ans += (rem[fx] == 0);
rem[fx] = 1;
}
cout << ans - 1 << endl;
return 0;
}
HDU1272_小希的迷宫
#include<bits/stdc++.h>
using namespace std;
static const int Maxn = 1e5 + 10;
int rem[Maxn], fa[Maxn], cnt;
bool flag;
void Init(){
for(int i = 1; i <= Maxn; i++) fa[i] = i;
memset(rem, 0, sizeof(rem));
flag = true; cnt = 0;
}
bool ask(){
if((!flag) || cnt > 1) return false;
return true;
}
int Find(int x){
if(x != fa[x]) fa[x] = Find(fa[x]);
return fa[x];
}
void query(int x, int y){
cnt += 2 - rem[x] - rem[y];
rem[x] = rem[y] = 1;
int fx = Find(x), fy = Find(y);
if(fx == fy) flag = false;
else {fa[fx] = fy; cnt--;}
}
int main(){
int x, y;
while(scanf("%d%d", &x, &y) && x != -1 && y != -1){
if(x == 0 && y == 0){
printf(ask() ? "Yes\n" : "No\n");
Init(); continue;
}
if(flag) query(x, y);
}
return 0;
}
HDU1233_还是畅通工程
#include<bits/stdc++.h>
using namespace std;
static const int Maxn = 110;
typedef struct{
int u, v, w;
}D;
D d[Maxn * Maxn];
int fa[Maxn];
void Init(int n){
for(int i = 1; i <= n; i++) fa[i] = i;
}
int Find(int x){
if(x != fa[x]) fa[x] = Find(fa[x]);
return fa[x];
}
bool cmp(D x, D y){
return x.w < y.w;
}
int main()
{
int n;
while(scanf("%d", &n) && n != 0){
Init(n);
int len = n * (n - 1) / 2, sum = 0;
for(int i = 0; i < len; i++) scanf("%d%d%d", &d[i].u, &d[i].v, &d[i].w);
sort(d, d + len, cmp);//边权排序
for(int i = 0; i < len; i++){
int fx = Find(d[i].u), fy = Find(d[i].v);
if(fx != fy){
fa[fx] = fy;
sum += d[i].w;
}
}
printf("%d\n", sum);
}
return 0;
}
HDU4496_D-City
#include<bits/stdc++.h>
using namespace std;
static const int Maxn = 1e4 + 10;
static const int Maxm = 1e5 + 10;
typedef pair <int ,int> P;
P p[Maxm];
int ans[Maxm], fa[Maxn];
void Init(int N){
for(int i = 0; i < N; i++) fa[i] = i;
}
int Find(int x){
if(x != fa[x]) fa[x] = Find(fa[x]);
return fa[x];
}
bool Query(int x, int y){
int fx = Find(x), fy = Find(y);
if(fx == fy) return false;
fa[fx] = fy; return true;
}
void Print(int M){
for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
}
int main(){
int N, M;//又TM是多组数据
while(scanf("%d%d", &N, &M) != EOF){
for(int i = 0; i < M; i++) scanf("%d%d", &p[i].first, &p[i].second);
Init(N);
ans[M] = N;
for(int i = M - 1; i >= 0; i--){
ans[i] = ans[i + 1];
if(Query(p[i].first, p[i].second)) ans[i] --;
}//如果加边的两点不属于一个块就ans--
Print(M);
}
return 0;
}
Poj1182_食物链
#include<bits/stdc++.h>
using namespace std;
class DisjointSet{
private:
int *fa, *r;
public:
DisjointSet(int size){
fa = new int[size];
r = new int[size];
for(int i = 1; i <= size; i++){
fa[i] = i; r[i] = 0;//relation 0同类，1被fa吃，2吃fa
}
}
~DisjointSet(){
delete [] fa;
delete [] r;
}
int find_set(int node){
if(node != fa[node]){
int pre = fa[node];//!
fa[node] = find_set(fa[node]);
r[node] = (r[node] + r[pre]) % 3;
}
return fa[node];
}
int solve(int d, int x, int y){
int fx = find_set(x), fy = find_set(y);
if(fx == fy){
if((r[y] - r[x] + 3) % 3 == d - 1) return 0;//!
else return 1;
}
fa[fy] = fx;//!
r[fy] = (r[x] - r[y] + d + 2) % 3;//!
return 0;
}
};
int main(){
int N, K, ans = 0, d, x, y;
cin >> N >> K;
DisjointSet dsu(N);
while(K--){
cin >> d >> x >> y;
if(x > N || y > N || (x == y && d == 2)) ans++;
else ans += dsu.solve(d, x, y);
}
cout << ans << endl;
return 0;
}
Poj2492_A Bug's Life
C语言
#include<stdio.h>
int fa[2010], r[2010];
bool flag;
int Find(int node){
if(node != fa[node]){
int pre = fa[node];
fa[node] = Find(fa[node]);
r[node] = (r[node] + r[pre]) % 2;
}
return fa[node];
}
int main(){
int T, n, k, kase = 0, x, y, fx, fy;
scanf("%d", &T);
while(T--){
flag = true;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++){ fa[i] = i; r[i] = 0;}
while(k--){
scanf("%d%d", &x, &y);
if(!flag) continue;
fx = Find(x); fy = Find(y);
if(fx != fy){
fa[fy] = fx;
r[fy] = (r[x] - r[y] + 1) % 2;
}
else if(r[x] == r[y]) flag = false;//这里不能加break！！！否则后面的输入操作就没了
}
if(kase > 0) printf("\n");
if(!flag) printf("Scenario #%d:\nSuspicious bugs found!\n", ++kase);
else printf("Scenario #%d:\nNo suspicious bugs found!\n", ++kase);
}
return 0;
}
C++
#include<cstdio>
using namespace std;
class DisjointSet{
private:
int *fa, *r;
public:
DisjointSet(int size){
fa = new int[size];
r = new int[size];
}
~DisjointSet(){
delete [] fa;
delete [] r;
}
void Init(int size){
for(int i = 1; i <= size; i++){
fa[i] = i; r[i] = 0;
}
}
int find_set(int node){
if(node != fa[node]){
int pre = fa[node];//!
fa[node] = find_set(fa[node]);
r[node] = (r[node] + r[pre]) % 2;
}
return fa[node];
}
bool solve(int x, int y){
int fx = find_set(x), fy = find_set(y);
if(fx == fy){
if(r[x] == r[y]) return false;//!
else return true;
}
fa[fy] = fx;//!
r[fy] = (r[x] - r[y] + 1) % 2;//!
return true;
}
};
int main(){
DisjointSet dsu(2010);
int T, kase = 0, n, k, x, y;
bool flag;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &k);
flag = true;
dsu.Init(n);
while(k--){
scanf("%d%d", &x, &y);
if(flag && !dsu.solve(x, y)) flag = false;//没有break没有beak没有beak
}
if(kase > 0) printf("\n");
if(!flag) printf("Scenario #%d:\nSuspicious bugs found!\n", ++kase);
else printf("Scenario #%d:\nNo suspicious bugs found!\n", ++kase);
}
return 0;
}
Poj1984_Navigation Nightmare
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
static const int Maxn = 4e4 + 10;
static const int Maxm = 4e4 + 10;
static const int Maxk = 1e4 + 10;
typedef struct{
int x, y, t;
}Query;
Query q[Maxk];
map <char, int> dir;
int fa[Maxn], ew[Maxn], sn[Maxn], x[Maxm], y[Maxm], len[Maxm];
char d[Maxm][10];
void Init(int size){
for(int i = 1; i <= size; i++) fa[i] = i;
dir['E'] = dir['S'] = 1;
dir['W'] = dir['N'] = -1;
}
int Find(int x){
if(x != fa[x]){
int pre = fa[x];
fa[x] = Find(fa[x]);
ew[x] += ew[pre]; sn[x] += sn[pre];
}
return fa[x];
}
void query(int x, int y){
int fx = Find(x), fy = Find(y);
if(fx != fy) printf("-1\n");
else printf("%d\n", abs(ew[x] - ew[y]) + abs(sn[x] - sn[y]));
}
bool cmp(Query a, Query b){
return a.t < b.t;
}
int main()
{
int n, m, k, j = 1;
scanf("%d%d", &n ,&m);
Init(n);
for(int i = 1; i <= m; i++) scanf("%d%d%d%s", &x[i], &y[i], &len[i], d[i]);
scanf("%d", &k);
for(int i = 1; i <= k; i++) scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].t);
sort(q, q + k, cmp);
for(int i = 1; i <= m; i++){
int fx = Find(x[i]), fy = Find(y[i]);
if(d[i][0] == 'E' || d[i][0] == 'W'){
fa[fy] = fx;
ew[fy] = ew[x[i]] - ew[y[i]] + dir[d[i][0]] * len[i];
sn[fy] = sn[x[i]] - sn[y[i]];
}
else{
fa[fy] = fx;
ew[fy] = ew[x[i]] - ew[y[i]];
sn[fy] = sn[x[i]] - sn[y[i]] + dir[d[i][0]] * len[i];
}
while(j <= k && q[j].t == i){query(q[j].x, q[j].y); j++;}
}
return 0;
}
Poj1988_Cube Stacking
#include<cstdio>
using namespace std;
static const int Maxn = 3e4 + 10;
int fa[Maxn], V[Maxn], r[Maxn];
/*
V[i]表示i所在堆的数量
r[i]表示i之下的块数
*/
void Init(){
for(int i = 1; i <= 3e4; i++){
fa[i] = i; V[i] = 1; r[i] = 0;
}
}
int Find(int x){
if(x != fa[x]){
int pre = fa[x];
fa[x] = Find(fa[x]);
V[x] = V[pre]; r[x] += r[pre];
}
return fa[x];
}
void Move(int x, int y){
int fx = Find(x), fy = Find(y);
fa[fx] = fy; r[fx] += V[fy]; V[fy] += V[fx];
}
void Count(int x){
Find(x);//更新上一次操作
printf("%d\n", r[x]);
}
int main(){
int P, x, y;
char opr[10];
scanf("%d", &P);
Init();
while(P--){
scanf("%s%d", opr, &x);
if(opr[0] == 'M'){
scanf("%d", &y); Move(x, y);
}
else Count(x);
}
return 0;
}
HDU3635_Dragon Balls
#include<bits/stdc++.h>
using namespace std;
static const int Maxn = 1e4+10;
int fa[Maxn], cnt[Maxn], t[Maxn], kase;
void Init(int N){
for(int i = 0; i <= N; i++){
fa[i] = i; cnt[i] = 1; t[i] = 0;
}
}
int Find(int x){
if(x != fa[x]){
int pre = fa[x];
fa[x] = Find(fa[x]);
cnt[x] = cnt[pre];
t[x] += t[pre];
}
return fa[x];
}
void Trans(int x, int y){
int fx = Find(x), fy = Find(y);
fa[fx] = fy;
cnt[fy] += cnt[fx];
t[fx]++;
}
void Query(int x){
Find(x);
printf("%d %d %d\n", fa[x], cnt[x], t[x]);
}
int main()
{
int T, N, k, x, y;
char opr[10];
scanf("%d", &T);
while(T--){
scanf("%d%d", &N, &k);
Init(N);
printf("Case %d:\n", ++kase);
while(k--){
scanf("%s%d", opr, &x);
if(opr[0] == 'T'){
scanf("%d", &y); Trans(x, y);
}
else Query(x);
}
}
return 0;
}
Poj1733_Parity game
自己打的vector
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
static const int Maxn = 5010;
typedef struct{
int u, v, w;
}Node;
Node d[Maxn];
vector <int> Hash;//可以用数组
int fa[Maxn * 2], r[Maxn * 2];
void init(int size){
for(int i = 0; i <= size; i++) fa[i] = i;
}
int Find(int x){
if(x != fa[x]){
int pre = fa[x];
fa[x] = Find(fa[x]); r[x] = r[x] ^ r[pre];
}
return fa[x];
}
bool query(int x, int y, int conf){
int fx = Find(x), fy = Find(y);
if(fx == fy){
if(r[x]^r[y] == conf) return true;
else return false;
}
if(fy < fx) swap(fy, fx);//这句话其实也可以不要
fa[fy] = fa[fx]; r[fy] = r[y] ^ conf ^ r[x];
return true;
}
int main(){
int n, k, x, y, ans = 0;
char s[10];
bool flag = true;
scanf("%d%d", &n ,&k);
for(int i = 0; i < k; i++){
scanf("%d%d%s", &d[i].u, &d[i].v, s);
d[i].w = (s[0] == 'e') ? 0 : 1;//奇偶处理
Hash.push_back(d[i].u - 1); //左闭右开，离散化
Hash.push_back(d[i].v);
}
sort(Hash.begin(), Hash.end());
n = unique(Hash.begin(), Hash.end()) - Hash.begin();//去重
init(n);
for(int i = 0; i < k && flag; i++){
x = lower_bound(Hash.begin(), Hash.begin() + n, d[i].u - 1) - Hash.begin();
y = lower_bound(Hash.begin(), Hash.begin() + n, d[i].v) - Hash.begin();
if(!query(x, y, d[i].w)) flag = false;
if(flag)ans++;
}
printf("%d", ans);
return 0;
}
用vector好傻 网上找的数组
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int fa[maxn], val[maxn], n, m;
int hashSet[maxn];
struct {
int u, v, w;
}node[maxn];
int find(int n){
int k = fa[n];
if(fa[n] != n){
fa[n] = find(fa[n]);
val[n] = (val[n] + val[k])%2;
}
return fa[n];
}
void init(){
for (int i = 0; i <= n; ++i)
val[i] = 0, fa[i] = i;
}
int main(){
while (~scanf("%d", &n)){
//init放这儿会RE，想想为什么，其实也可以不炸。。
int i, k = 0;
scanf("%d%d", &n, &m);
for (i = 0; i < m; ++i){
char s[5];
scanf("%d%d%s", &node[i].u, &node[i].v, s);
node[i].w = s[0] == 'e'? 0 : 1;
hashSet[k++] = node[i].u - 1;
hashSet[k++] = node[i].v;
}
sort(hashSet, hashSet+k);
n = (int)(unique(hashSet, hashSet+k) - hashSet);
init();
for (i = 0; i < m; ++i){
int u = (int)(lower_bound(hashSet, hashSet + n, node[i].u-1) - hashSet);
int v = (int)(lower_bound(hashSet, hashSet + n, node[i].v) - hashSet);
int fu = find(u), fv = find(v);
if (fu == fv && (val[u] + node[i].w)%2 != val[v])
break;
if (fu < fv){
fa[fv] = fu;
val[fv] = (val[u] + node[i].w - val[v] + 2) % 2;
}
if (fu > fv){
fa[fu] = fv;
val[fu] = (val[v] - node[i].w - val[u] + 2) % 2;
}
}
printf("%d\n", i);
}
return 0;
}
HDU3038_How Many Answers Are Wrong
#include<bits/stdc++.h>
using namespace std;
static const int Maxn = 2e5+10;
int fa[Maxn];
int r[Maxn];
void Init(int N){
for(int i = 0; i <= N; i++){
fa[i] = i; r[i] = 0;
}
}
int Find(int x){
if(x != fa[x]){
int pre = fa[x];
fa[x] = Find(fa[x]);
r[x] += r[pre];
}
return fa[x];
}
bool Query(int x, int y, int sum){// (x-1, y] 左闭右开
int fx = Find(x), fy = Find(y);
if(fx == fy){
if(r[x] + sum == r[y]) return true;
else return false;
}
fa[fy] = fx;
r[fy] = r[x] + sum - r[y];
return true;
}
int main(){
int N, M, x, y, sum, ans;
//多组测试数据（题目好像没说，卡了我好久
while(scanf("%d%d", &N, &M) != EOF){
ans = 0;
Init(N);
while(M--){
scanf("%d%d%d", &x, &y, &sum);
if(!Query(x - 1, y, sum)) ans++;
}
printf("%d\n", ans);
}
return 0;
}
最后贴个网上找的可持久化并查集模板题的题解，看了好久终于看懂了 自己打的话估计bug连连
有时间补几道可持久化的题 不可能的 TMD好难
#include<bits/stdc++.h>
#define N 301000
using namespace std;
template<typename T>inline void read(T &x)
{
x=0;
static int p;p=1;
static char c;c=getchar();
while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
x*=p;
}
int n,m;
int L[N*30],R[N*30],fa[N*30],dep[N*30];
int root[N*30];
namespace Persistant_Union_Set
{
#define Mid ((l+r)>>1)
#define lson L[rt],l,Mid
#define rson R[rt],Mid+1,r
int cnt;
void build(int &rt,int l,int r)
{
rt=++cnt;
if(l==r){fa[rt]=l;return ;}
build(lson);build(rson);
}
void merge(int last,int &rt,int l,int r,int pos,int Fa)
{
rt=++cnt;L[rt]=L[last],R[rt]=R[last];
if(l==r)
{
fa[rt]=Fa;
dep[rt]=dep[last];
return;
}
if(pos<=Mid)merge(L[last],lson,pos,Fa);
else merge(R[last],rson,pos,Fa);
}
void update(int rt,int l,int r,int pos)
{
if(l==r){dep[rt]++;return ;}
if(pos<=Mid)update(lson,pos);
else update(rson,pos);
}
int query(int rt,int l,int r,int pos)
{
if(l==r)return rt;
if(pos<=Mid)return query(lson,pos);
else return query(rson,pos);
}
int find(int rt,int pos)
{
int now=query(rt,1,n,pos);
if(fa[now]==pos)return now;
return find(rt,fa[now]);
}
#undef Mid
#undef lson
#undef rson
}
using namespace Persistant_Union_Set;
int main()
{
read(n);read(m);
build(root[0],1,n);
for(int i=1;i<=m;i++)
{
static int opt,x,y;
read(opt);read(x);
if(opt==1)
{
read(y);
static int posx,posy;
root[i]=root[i-1];
posx=find(root[i],x);posy=find(root[i],y);
if(fa[posx]!=fa[posy])
{
if(dep[posx]>dep[posy])swap(posx,posy);
merge(root[i-1],root[i],1,n,fa[posx],fa[posy]);
if(dep[posx]==dep[posy])update(root[i],1,n,fa[posy]);
}
}
else if(opt==2)root[i]=root[x];
else if(opt==3)
{
read(y);
root[i]=root[i-1];
static int posx,posy;
posx=find(root[i],x);posy=find(root[i],y);
if(fa[posx]==fa[posy])puts("1");
else puts("0");
}
}
return 0;
}
