# 目次

• 目次
  • 解答1 | 単純な深さ優先探索による解法
    • 時間制限超過
  • 解答2 | 深さ優先探索の応用によるノード分類
    • 合格

# 解答1 | 単純な深さ優先探索による解法

# 時間制限超過

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

bool dfs(vector<Int> vs[], Int n, Int source, Int target) {
    if (source == target) return true;
    
    bool visited[n];
    loop(i,0,n)  visited[i] = false;
    
    stack<Int> S;
    S.push(source);
    visited[source] = true;
    
loop:
    while (!S.empty()) {
        Int i = S.top();
        for (auto c: vs[i]) {
            if (visited[c]) continue;
            if (c == target) return true;
            S.push(c);
            visited[c] = true;
            goto loop;
        }
        
        S.pop();
    }
    
    return false;
}

bool connected(vector<Int> vs[], Int n, Int s, Int t) {
    return dfs(vs, n, s, t);
}

int main(void) {
    Int n, m, q, v, x;
    cin >> n >> m;
    vector<Int> vs[n];
    loop(i,0,m) {
        cin >> v >> x;
        vs[v].push_back(x);
        vs[x].push_back(v);
    } 
    
    cin >> q;
    loop(i,0,q) {
        cin >> v >> x;
        if (connected(vs, n, v, x)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

# 解答2 | 深さ優先探索の応用によるノード分類

# 合格

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

void dfs_color(vector<Int> vs[], Int colors[], Int n) {
    bool visited[n];
    loop(i,0,n)  {
        visited[i] = false;
        colors[i] = 0;
    }
    
    stack<Int> S;
    
    loop(i,0,n) {
        Int color = i + 1;
        S.push(i);
        visited[i] = true;
        if (colors[i] == 0) colors[i] = color;
        
out_of_while:
        while (!S.empty()) {
            Int i = S.top();
            for (auto c: vs[i]) {
                if (visited[c]) continue;
                S.push(c);
                visited[c] = true;
                if (colors[c] == 0) colors[c] = color;
                goto out_of_while;
            }
            
            S.pop();
        }
    }
}


int main(void) {
    Int n, m, q, v, x;
    cin >> n >> m;
    vector<Int> vs[n];
    Int colors[n];
    
    loop(i,0,m) {
        cin >> v >> x;
        vs[v].push_back(x);
        vs[x].push_back(v);
    } 
    
    dfs_color(vs, colors, n);
    
    cin >> q;
    loop(i,0,q) {
        cin >> v >> x;
        if (colors[v] == colors[x]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}