グラフの連結成分をALDS1_11_D:Connected Componentsを利用してc++で学ぶ

グラフの連結成分に関してALDS1_11_D:Connected Componentsを参考にして学びます。

問題文

連結成分分解
SNS の友達関係を入力し、
双方向の友達リンクを経由してある人からある人へたどりつけるかどうかを判定するプログラムを作成してください。

入力

１行目にSNS のユーザ数を表す整数 nn と友達関係の数 mm が空白区切りで与えられます。
SNS の各ユーザには 0 から n－1 までのID が割り当てられています。

続く mm 行に１つの友達関係が各行に与えられます。
１つの友達関係は空白で区切られた２つの整数 ss、tt で与えられ、ss と tt が友達であることを示します。

続く１行に、質問の数 qq が与えられます。続くqq 行に質問が与えられます。
各質問は空白で区切られた２つの整数 ss、tt で与えられ、「ss から tt へたどり着けますか？」という質問を意味します。

出力

各質問に対して ss から tt にたどり着ける場合は yes と、たどり着けない場合は no と１行に出力してください。

入力例

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

出力例

yes
yes
no

同じグループに属するか判定する処理

色を振り分けることにより同じグループに属するかどうかを判定します。

void assignColor(int number){
    int id = 1;
    for(int i = 0;i < number;++i){
        color[i] = NIL;
    }
    for(int i = 0;i < number;++i){
        if(color[i] == NIL)dfs(i,id++);
    }
}

続いて深さ優先探索にて、自身の友達に対し色を割り当てます。
これを元にして、探索を行います。

void dfs(int r,int c){
    stack<int>s;
    // 自身を入れる
    s.push(r);
    // colorに自信のidを入れる
    color[r] = c;
    while(!s.empty()){
        // 自身
        int u = s.top();
        s.pop();
        // 自分の友達に色を割り当てる
        for(int i = 0;i < gGraph[u].size();++i){
            int v = gGraph[u][i];
            if(color[v] == NIL){
                color[v] = c;
                s.push(v);
            }
        }
    }
}

では、 c++の解答例です。

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

#define MAX 1000000
#define NIL -1

vector<int>gGraph[MAX];
int color[MAX];

void dfs(int r,int c){
    stack<int>s;
    // 自身を入れる
    s.push(r);
    // colorに自信のidを入れる
    color[r] = c;
    while(!s.empty()){
        // 自身
        int u = s.top();
        s.pop();
        // 自分の友達に色を割り当てる
        for(int i = 0;i < gGraph[u].size();++i){
            int v = gGraph[u][i];
            if(color[v] == NIL){
                color[v] = c;
                s.push(v);
            }
        }
    }
}

void assignColor(int number){
    int id = 1;
    for(int i = 0;i < number;++i){
        color[i] = NIL;
    }
    // 同じグループに属するかの色を割り当てる
    for(int i = 0;i < number;++i){
        if(color[i] == NIL)dfs(i,id++);
    }
}

int main(){
    int s,t,m,q,n;
    
    cin >> n >> m;
    
    // 友達関係数
    for(int i = 0;i < m;++i){
        cin >> s >> t;
        // 各々のインデックスごとに友達を加算する
        gGraph[s].push_back(t);
        gGraph[t].push_back(s);
    }
    
    assignColor(n);
    
    cin >> q;
    
    for(int i = 0;i < q;++i){
        cin >> s >> t;
        if(color[s] == color[t]){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
    return 0;
}

参考資料 https://book.mynavi.jp/ec/products/detail/id=35408