【AOJ ALDS1_11】D: Graph I - Connected Components

問題

グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

グラフの連結成分(Connected Components)を求める問題.
連結成分とは, 必ずしも連結でないグラフGに対して, その極大連結部分グラフのことをグラフGの連結成分という.
G'がGの極大連結部分グラフであるとは, 1) G'がGの部分連結グラフであること 2) G'を部分グラフとして持つようなGの連結部分グラフが存在しないことが満たされているものを言う.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<stack>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define MAX_N 100001

using namespace std;

vector<int> G[MAX_N];
int label[MAX_N];

void dfs(int start, int id){
  stack<int> s;
  s.push(start);
  label[start] = id;
  while(!s.empty()){
    int u = s.top(); s.pop();
    rep(i, G[u].size()){
      int v = G[u][i];
      if(label[v] == -1){
    label[v] = id;
    s.push(v);
      }
    }
  }
}

void solve(int n){
  int id = 1;

  rep(u, n){
    if(label[u] == -1){
      dfs(u, id);
      id++;
    }   
  }
}

void init(){
  rep(i, MAX_N) label[i] = -1;
}

signed main(){
  int n, m, s, t;
  cin >> n >> m;
  rep(i, m){
    cin >> s >> t;
    G[s].pb(t);
    G[t].pb(s);
  }

  init();
  solve(n);

  int q;

  cin >> q;
  rep(i, q){
    cin >> s >> t;
    if(label[s] == label[t]){
      cout << "yes" << endl;
    }else{
      cout << "no" << endl;
    }
  }
}