union

union

Union 模板

int n = 1005;
vector<int> father = vector<int> (n, 0);
 
// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集尋根過程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路徑壓縮
}
 
// 判斷 u 和 v是否找到同一個根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
 
// 將v->u 這條邊加入并查集
void join(int u, int v) {
    u = find(u); // 尋找u的根
    v = find(v); // 尋找v的根
    if (u == v) return ; // 如果發現根相同，則在一个集合，不用两個節點相連，直接返回
    father[v] = u;
}

Union按rank合併

int n = 1005; // n根據題目定義，一般比節點大一點即可
vector<int> father = vector<int> (n, 0);
vector<int> rank = vector<int> (n, 1); // 初始化每棵樹高度為1
 
// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        rank[i] = 1; // 可以省略
    }
}
// 并查集尋找根過程
int find(int u) {
    return u == father[u] ? u : find(father[u]);// 注意這裏不做路徑壓縮
}
 
// 判斷 u 和 v是否找到同一個根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
 
// 將v->u 這條邊加入并查集
void join(int u, int v) {
    u = find(u); // 尋找u的根
    v = find(v); // 尋找v的根
 
    if (rank[u] <= rank[v]) father[u] = v; // rank小的樹合入到rank大的樹
    else father[v] = u;
 
    if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵樹高度相同，則v的高度+1，因為上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}

Hdu1213

  • 題目要求好友關系，如果A認識B就會做一起，只需要一張桌子，現在來個C不認識自己也一張
    • 用union來將認識的合併，在統計有多少集合
  • 注意題目從1開始
#include <iostream>
using namespace std;
 
const int N = 1050;
int s[N];
 
void init_set(){
    for(int i=1;i<=N;i++) s[i] = i;
}
 
int find_set(int x) {
    if(x != s[x]) s[x] = find_set(s[x]);
    return s[x];
}
 
void merge_set(int x,int y){
    x=find_set(x);y=find_set(y);
    if(x!=y)s[x]=s[y];
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t,m,n,x,y;
    cin >> t;
    while(t--){
        cin >> n >> m;
        init_set();
        for(int i=1;i<=m;i++){
            cin >> x >> y;
            merge_set(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(s[i]==i)ans++;
        }
        cout << ans << '\n';
    }
}

帶權并查集

  • 路徑壓縮
    • d[1]' = d[1]+d[2]+d[3]
  • 先用t紀錄x的父節點，在遞迴過程中最後返回的是根節點，最後再將當前節點的權重加上原父節點的權重
    • 經過遞迴，此時父節點也指向根節點，父節點權重已經更新為父節點直接到根節點權重
int find_set(int x){
  if(x != s[x]){
    int t = s[x];
    s[x] = find_set(s[x]);
    d[x] += d[t];
  }
  return s[x];
}
  • 合併
    • 把點x和點y合併，就是將x的根節點fx合併到y的根節點fy，在fx和fy之間增加權重

hdu3038

#include <iostream>
using namespace std;
 
const int N = 200010;
 
int s[N];
int d[N];
 
void init_set(int n){
    for(int i=0; i<= n;i++) {s[i]=i;d[i]=0;};
}
 
int find_set(int x){
    if(x != s[x]){
        int t = s[x];
        s[x] = find_set(s[x]);
        d[x] += d[t];
    }
    return s[x];
}
 
void mearge_set(int a,int b,int v,int&ans){
    int roota = find_set(a);
    int rootb = find_set(b);
    if(roota == rootb) {
        if(d[a]-d[b] != v) ans++;
    }else{
        s[roota]=rootb;
        d[roota]=d[b]-d[a]+v;
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF){
        init_set(n);
        int ans=0;
        while(m--){
            int a,b,v;
            scanf("%d%d%d",&a,&b,&v);
            a--;
            mearge_set(a,b,v,ans);
        }
        printf("%d\n",ans);
    }
}

poj1182

  • 路徑壓縮更新權重規律

    • 0表示同類,1表示吃,2表示被吃
    • d(a->b)=1 d(b->c)=1 d(a->c)=2
    • d(a->b)=2 d(b->c)=2 d(a->c)=1
    • d(a->b)=0 d(b->c)=1 d(a->c)=1

  • 由規律可發覺d(a->c)=(d(a->b)+d(b->c))%3

  • relation-1是為了讓區間限制在[0,1,2]，因為我們有取mod操作

cin會超時

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 50005;
 
int s[N];
int d[N];
int ans;
void init_set(int n){
    for(int i=0;i<=n;i++){
        s[i]=i;
        d[i]=0;
    }
}
 
int find_set(int x){
    if(x != s[x]){
        int t = s[x];
        s[x] = find_set(s[x]);
        d[x] = (d[x]+d[t])%3;
    }
    return s[x];
}
 
void merage_set(int x,int y,int relation){
    int roota = find_set(x);
    int rootb = find_set(y);
    if(roota==rootb){
        if((relation-1)!=((d[x]-d[y]+3)%3))ans++;
    }else{
        s[roota]=rootb;
        d[roota]=(d[y]-d[x]+relation-1)%3;
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    int n,k;scanf("%d%d",&n,&k);
    init_set(n);
    ans=0;
    while(k--){
        int relation,x,y;scanf("%d%d%d",&relation,&x,&y);
        if(x>n || y>n || (relation==2&&x==y))ans++;
        else merage_set(x,y,relation);
    }
    printf("%d",ans);
    return 0;
}

poj2236

  • 從0開始所以要減1
#include <iostream>
using namespace std;
 
const int N = 1050;
int s[N];
int x[N];
int y[N];
bool m[N];
int r[N];
 
int find_set(int x){
    if(x != s[x]) s[x] = find_set(s[x]);
    return s[x];
}
 
void merage(int a,int b){
    int roota = find_set(a);
    int rootb = find_set(b);
    if(roota != rootb) s[roota] = rootb;
}
 
int dis(int a,int b){
    return (((x[a] - x[b]) * (x[a] - x[b]))+((y[a] - y[b]) * (y[a] - y[b])));
}
 
int main()
{
    int n, d;
    cin >> n >> d;
    for(int i=1;i<=n;i++){
        cin >> x[i-1] >> y[i-1];
        s[i] = i;
        m[i] = false;
    }
    char c;
    int p;
    int idx=0;
    while(cin >> c){
        if(c == 'O'){
            cin >> p;
            p--;
            r[idx++] = p;
            for(int i=0;i<idx;i++){
                if(dis(r[i],p) <= d*d) merage(r[i],p);
            }
        }else if(c =='S'){
            int l=0,r=0;
            cin >> l >> r;
            l--;r--;
            int rootl = find_set(l);
            int rootr = find_set(r);
            rootl == rootr ? cout << "SUCCESS" << '\n' : cout << "FAIL" << '\n';
        }
    }
}

poj1611

  • 加入并查集後找是否有和0相同的根
  • 初始化要從0開始!

當一次要輸入很多值進union，可用以下方式

      int q, n1;
            cin >> q >> n1;
            for (int i = 1; i < q; i++)
            {
                int n;
                cin >> n;
                merage(n1, n);
                n1 = n;
            }
#include <iostream>
using namespace std;
 
const int N = 30050;
int s[N];
 
void init_set(int n){
    for(int i=0;i<n;i++) s[i] = i;
}
 
int find_set(int x){
    if(x != s[x]) s[x]=find_set(s[x]);
    return s[x];
}
 
void merage(int a,int b){
    int roota = find_set(a);
    int rootb = find_set(b);
    if(roota != rootb) s[roota] = rootb;
}
 
int main(){
    int n,m;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin >> n >> m){
        if(n == 0 && m == 0) break;
        init_set(n);
        while (m--)
        {
            int q, n1;
            cin >> q >> n1;
            for (int i = 1; i < q; i++)
            {
                int n;
                cin >> n;
                merage(n1, n);
                n1 = n;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (find_set(s[i]) == find_set(0))
                ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

ACM107

#include <iostream>
using namespace std;
 
const int N = 105;
int s[N];
 
void init(int n){
    for(int i=0;i<n;i++) s[i]=i;
}
 
int find_set(int x){
  if(x != s[x]) s[x] = find_set(s[x]);
  return s[x];
}
 
void merage(int a,int b){
  int roota = find_set(a);
  int rootb = find_set(b);
  if(roota != rootb) s[roota] = rootb;
}
 
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
  int n,m,s,t,source,destination;
  cin >> n >> m;
  init(n);
  while(m--){
    cin >> s >> t;
    merage(s,t);
  }
  cin >> source >> destination;
  find_set(source) == find_set(destination) ? cout << 1 << '\n' : cout << 0 << '\n';
}

ACM108

#include <iostream>
 
using namespace std;
 
const int N = 1050;
 
int s[N];
 
void init(int n){
  for(int i =0;i<n;i++)s[i]=i;
}
 
int find_set(int x){
  if(x != s[x]) s[x] = find_set(s[x]);
  return s[x];
}
 
void join(int a,int b){
  int roota = find_set(a);
  int rootb = find_set(b);
  if(roota != rootb) s[roota] = rootb;
}
 
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
  int n;cin>>n;
  init(n);
  while(n--){
    int s,t;cin>>s>>t;
    if(find_set(s)==find_set(t)){
      cout << s << " " << t;
      break;
    }else{
      join(s,t);
    }
  }
  return 0;
}

ACM109

  • isTreeAfterRemove判斷有邊的情況，之所以先判斷vc[0]是由於放入vc是倒敘的緣故
  • 在紀錄邊的時候i從n-1是題目要求從做後一個刪
#include <iostream>
#include <vector>
using namespace std;
 
int n =0;
vector<int>s(1001,0);
 
void init_set(){
  for(int i=1;i<=n;i++)s[i]=i;
}
 
int find_set(int x){
  if(x != s[x]) s[x] = find_set(s[x]);
  return s[x];
}
 
void join(int x,int y){
  int rootx = find_set(x);
  int rooty = find_set(y);
  if(rootx != rooty) s[rootx] = rooty;
}
 
bool isTreeAfterRemove(vector<vector<int>>&edges,int deleteEdge){
  init_set();
  for(int i=0;i<n;i++){
      if(i == deleteEdge) continue;
      if(find_set(edges[i][0]) == find_set(edges[i][1])){
        return false;
      }else{
        join(edges[i][0],edges[i][1]);
    }
  }
  return true;
}
 
void getRemoveEdge(vector<vector<int>>&edges){
  init_set();
  for(int i=0;i<n;i++){
    if(find_set(edges[i][0]) == find_set(edges[i][1])){
      cout << edges[i][0] << " " << edges[i][1];
      return;
    }else{
      join(edges[i][0], edges[i][1]);
    }
  }
}
 
int main(){
  vector<vector<int>> edges;
  cin >> n;
 
  vector<int>isDrgee(n+1,0);
  for(int i=0;i<n;i++){
    int s,t;cin >> s >> t;
    // 紀錄節點
    edges.push_back({s,t});
    // 紀錄邊為2的節點
    isDrgee[t]++;
  }
  vector<int> vc;
  //紀錄邊為2的入vc等刪除
  for(int i=n-1;i >=0;i--){
    if(isDrgee[edges[i][1]]== 2){
      vc.push_back(i);
    }
  }
 
  // 邊為2的要判斷刪除後是否還是樹
  if(vc.size() > 0){
    if(isTreeAfterRemove(edges,vc[0])){
      cout << edges[vc[0]][0] << " " << edges[vc[0]][1];
    }else{
      cout << edges[vc[1]][0] << " " << edges[vc[1]][1];
    }
    return 0;
  }
 
  // 沒有邊為2的必定有有向環，處理有向環即可返回
  getRemoveEdge(edges);
}