[ALDS_1_11_D] 深さ優先探索アルゴリズムの隣接リストパターンはスタックで

AOJのALDS１＿１１＿D: Connected Componentsの問題を解いてみました。こちらのプログラムはSNSなどで相互フォロー関係をたどり、任意の相手にたどりつくことができるかを判定するものです。とりあえずプログラムはこちら。

#include <iostream>
#include <vector>
#include <stack>
#define MAX 100000
#define NIL -1

using namespace std;

int n, m, s, t, q;
vector<int> G[MAX];
int group[MAX];

//深さ優先探索で頂点間の関係性を決定します。
void dfs(int r, int c){
    stack<int> S;// stackでバッファリング
    S.push(r);
    group[r] = c;// その頂点rをgroupに分類
    while(!S.empty()){
        int u = S.top(); S.pop(); // stackから頂点を取り出す
        for(int i=0; i<G[u].size(); i++){ //隣接リストで頂点uに隣接する頂点を探す
            int v = G[u][i] //隣接する頂点vを取り出す
            if(group[v]==NIL){ // 隣接する頂点vがどこかの隣接する頂点グループに属するかを判定
                group[v]=c;// どこの頂点の隣接でもなければ、頂点vをcグループとして分類
                S.push(v);//このまま頂点vの隣接頂点の状態を探索するために頂点vをstack
            }
        }
    }
}

void makeGroup(){
    int id =1;
    for(int i=0; i<n;i++){//グループの初期化
        group[i]=NIL;
    }
    for(int u=0; u<n; u++){
        if(group[u]==NIL){//グループに所属していない頂点について深さ優先探索していく
            dfs(u,id++);
        }
    }
}

int main(){

    cin >> n >> m;

    for(int i=0; i < m; i++){
            cin >> s >> t;
            G[s].push_back(t);// 頂点sと頂点tは友人関係、つまり無向グラフとして表現される
            G[t].push_back(s);// 頂点sと頂点tは友人関係、つまり無向グラフとして表現される
    }

    makeGroup();

    cin >> q;

    for(int i=0; i < q; i++){
        cin >> s >> t;
        if(group[s]==group[t]){//頂点sと頂点tが同一グループに所属するかを判定。同一グループであるなら、友人を経由してsとtはつながることが可能
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }

    return 0;

}

stackでデータを保持するのがポイントです。グループ未所属で、現在の頂点に隣接する頂点を深さ優先探索によって探索し、グループの状況を判定し、グループわけを実行していきます。

 - コンピュータサイエンス, アルゴリズム