模板

模板分为三大部分

• 初始化
• 查询i的祖先
• 合并i j(使他们祖先成为一个人)

// 1 初始化
void init(int n)
{for (int i = 1; i <= n; i++)fa[i] = i;//将该数的父节点定义为该数
}

// 2 查询i的祖先
int find(int i)
{if (i == fa[i])return i;else{![查](../pic/并查集.png)fa[i] = find(fa[i]);return fa[i];}
}

// 3 合并序列 将i的父节点设置为j
void unionn(int i, int j)
{int fi = find(i);int fj = find(j);fa[fi] = fj;
}

例题

步骤

#include<iostream>
using namespace std;
int f[1000010];
int a[1000010];
int b[1000010];
int c[1000010];
void init(int x)
{for (int i = 1; i <= x; i++){f[i] = i;}
}
int find1(int x)
{if (f[x] == x) return x;else{f[x] = find1(f[x]);return f[x];}
}
void union1(int x, int y)
{int fx = find1(x);int fy = find1(y);f[fx] = fy;
}int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= m; i++){int x, y, z;cin >> a[i] >> b[i] >> c[i];init(b[i]);init(c[i]);}for(int i = 1;i<=m;i++){ if (a[i] == 1) union1(b[i], c[i]);if (a[i] == 2){if (find1(b[i]) == find1(c[i])){cout << "Y" << endl;}else{cout << "N" << endl;}}}return 0;
}