Union-Find

前回の続き

全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索

茶色diff埋めをしていましたが、D - Friendsが茶色diffの為に先にUnion-Findを学習します。

Union-Find

Union-Findの解説

問題

DSL_1_A - 互いに素な集合

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class UnionFind{
private:
    vector<int> par_;

public:
    UnionFind(int N) : par_(N){
        rep(i, N) par_[i] = i;
    }

    int root(int x){
        if(par_[x] == x) return x;
        return root(par_[x]);
    }

    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);

        if(rx == ry) return;
        par_[rx] = ry;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(int argc, const char * argv[]) {
    int n, q;
    cin >> n >> q;

    UnionFind uni(n);

    rep(i, q){
        int cmd, x, y;
        cin >> cmd >> x >> y;

        if(cmd == 0) uni.unite(x, y);
        else if(cmd == 1){
            if(uni.same(x, y)) cout << 1 << endl;
            else  cout << 0 << endl;
        }
    }

    return 0;
}

C - Bridge

日本語が難しい問題でした。
Mの要素の一つを使うのをやめる（辺を取り除く）時、他の頂点と辺が連結していない（自身が親要素である）ならば橋である。
判定方法はMの要素の一つを使うのをやめた時、元々の親要素と新しく親要素が存在している（親要素が２つ以上）なら橋である。
制約として「また、M個の情報から導くことができない友達関係は存在しません。」があるので初期時には全ての頂点が１辺以上で連結しています。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class UnionFind{
    vector<int> par_;

public:
    UnionFind(int N) : par_(N){
        rep(i, N) par_[i] = i;
    }

    int root(int x){
        if(par_[x] == x) return x;
        return par_[x] = root(par_[x]);
    }

    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);

        if(rx == ry) return;
        par_[rx] = ry;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;

    vector<P> v(m);
    rep(i, m){
        cin >> v[i].first >> v[i].second;
        v[i].first--;
        v[i].second--;
    }

    int res=0;
    rep(i, m){
        UnionFind uni(n);
        rep(j, m){
            if(i != j && !uni.same(v[j].first, v[j].second)){
                uni.unite(v[j].first, v[j].second);
            }
        }
        set<int> s;
        rep(j, n){
            if(uni.root(j) == j) s.insert(j);
        }
        if(s.size()>1) res++;
    }
    cout << res << endl;
    return 0;
}

D - Friends

ルートの配列の要素に-1の負の数を加算していきグループ人数をカウントしていきます。
子の要素には親のindexを代入します。
サイズ取得時に正の数に変換します。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class UnionFInd{
    vector<int> par_;
public:
    UnionFInd(int n):par_(n){
        rep(i, n) par_[i] = -1;
    }

    int root(int x){
        if(par_[x] < 0) return x;
        return par_[x] = root(par_[x]);
    }

    bool unite(int x, int y){
        int rx = root(x);
        int ry = root(y);

        if(rx == ry) return false;
        if (par_[rx] > par_[ry]) swap(rx, ry);
        par_[rx] += par_[ry];
        par_[ry] = rx;
        return true;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x){
        return -par_[root(x)];
    }
};

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;

    UnionFInd uni(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        uni.unite(a, b);
    }
    int res = 0;
    for (int i=0; i<n; i++) res = max(res, uni.size(i));
    cout << res << endl;

    return 0;
}