Help us understand the problem. What is going on with this article?

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の要素の一つを使うのをやめた時、元々の親要素と新しく親要素が存在している(親要素が2つ以上)なら橋である。
制約として「また、M個の情報から導くことができない友達関係は存在しません。」があるので初期時には全ての頂点が1辺以上で連結しています。

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;
}
RubyLrving
エンジニア。 c/c++、pythonをメインで記述しています。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away