寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

アルゴ式（beta版）: C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)

プログラミング C++

アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。

C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)の解答例

僕が作成、提出したコードは、以下のとおりです。

Q5-1. 連結成分

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)の解答例
Q5-1. 連結成分
https://algo-method.com/tasks/431
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
vector<bool> is_visit;
void DFS(const vector<vector<int>>& graph,int i){
    is_visit[i]=true;
    for(auto j : graph[i]){
        if(is_visit[j]==false){
            DFS(graph,j);
        }
    }
}
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(m),b(m);
    vector<vector<int>> graph(n);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    is_visit.assign(n,false);
    int ans=0;
    for(int i=0;i<n;i++){
        if(is_visit[i]==false){
            DFS(graph,i);
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
Q5-2. 連結成分の最小値

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)の解答例
Q5-2. 連結成分の最小値
https://algo-method.com/tasks/558
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(m),b(m);
    vector<vector<int>> graph(n);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    vector<bool> is_visit(n);
    queue<int> q;
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        while(i<n && is_visit[i]){
            i++;
        }
        if(i==n){
            break;
        }
        for(q.push(i);!(q.empty());q.pop()){
            int j=q.front();
            ans[j]=i;
            for(int k : graph[j]){
                if(is_visit[k]){
                    continue;
                }
                is_visit[k]=true;
                q.push(k);
            }
        }
    }
    for(int& i : ans){
        cout<<i<<endl;
    }
    return 0;
}
Q5-3. Union-Find

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)の解答例
Q5-3. Union-Find
https://algo-method.com/tasks/559
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
struct UnionFind{
    vector<int> v1,v2,v3;
    UnionFind(int n) : v1(n,-1),v2(n,0),v3(n,-1) {}
    int root(int x){
        if(v1[x]==-1){
            return x;
        }else{
            return (v1[x]=root(v1[x]));
        }
    }
    bool is_same(int x,int y){
        return (root(x)==root(y));
    }
    bool unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry){
            return false;
        }
        if(v3[rx]<v3[ry]){
            swap(rx,ry);
        }
        v1[ry]=rx;
        if(v2[rx]==v2[ry]){
            v2[rx]++;
            v3[rx]+=v3[ry];
            return true;
        }
    }
};
int main(void){
    int n,m;
    cin>>n>>m;
    UnionFind uf(n);
    for(int i=0;i<m;i++){
        int A,B;
        cin>>A>>B;
        if(uf.is_same(A,B)){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
            uf.unite(A,B);
        }
    }
    return 0;
}
Q5-4. グループ分け問題

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)の解答例
Q5-4. グループ分け問題
https://algo-method.com/tasks/560
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
//前問でのUnionFindとは少しだけ違った実装
struct UnionFind{
    vector<int> parent;
    UnionFind(int n){
        parent=vector<int>(n,-1);
    }
    int root(int x){
        if(parent[x]<0){
            return x;
        }else{
            return (parent[x]=root(parent[x]));
        }
    }
    bool is_same(int x,int y){
        return (root(x)==root(y));
    }
    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry){
            return;
        }
        if(parent[rx]<parent[ry]){
            parent[rx]=min(parent[rx],parent[ry]-1);
            parent[ry]=rx;
        }else{
            parent[ry]=min(parent[ry],parent[rx]-1);
            parent[rx]=ry;
        }
    }
};
int main(void){
    int n,m;
    cin>>n>>m;
    UnionFind uf(n);
    vector<int> a(m),b(m);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        if(!uf.is_same(a[i],b[i])){
            n--;
            uf.unite(a[i],b[i]);
        }
        cout<<n<<endl;
    }
    return 0;
}
Q5-5. 粘土の重さ

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」10章:Union-Find (グループ分け)の解答例
Q5-5. 粘土の重さ
https://algo-method.com/tasks/561
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//前問でのUnionFindとは細かなところが違う.
//新たな関数も実装.
struct UnionFind{
	ll n;
    vector<ll> parent;
    UnionFind(ll n,vector<ll>& a){
        parent=vector<ll>(n);
		for(int i=0;i<n;i++){
			parent[i]=-a[i];
		}
    }
    ll root(ll x){
        if(parent[x]<0){
            return x;
        }else{
            return (parent[x]=root(parent[x]));
        }
    }
	ll root_weight(ll x){
		return -parent[root(x)];
	}
    bool is_same(ll x,ll y){
        return (root(x)==root(y));
    }
    void unite(ll x,ll y){
        ll rx=root(x),ry=root(y);
        if(rx==ry){
            return;
        }
        if(parent[rx]<parent[ry]){
            parent[rx]=parent[rx]+parent[ry];
            parent[ry]=rx;
        }else{
            parent[ry]=parent[rx]+parent[ry];
            parent[rx]=ry;
        }
    }
};
int main(void){
	ll n,q;
	cin>>n>>q;
	vector<ll> w(n);
	for(ll i=0;i<n;i++){
		cin>>w[i];
	}
	UnionFind uf(n,w);
	for(ll i=0;i<q;i++){
		ll t,x,y;
		cin>>t>>x>>y;
		if(t==0){
			uf.unite(x,y);
		}else{
			cout<<uf.root_weight(x)<<endl;
		}
	}
	return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com