aoj

# ALDS1_11_D Connected Components

ALDS1_11_D Connected Components
Feb. 2, 2020, 1:52 p.m.

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

### 時間制限超過

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 bool dfs(vector vs[], Int n, Int source, Int target) { if (source == target) return true; bool visited[n]; loop(i,0,n) visited[i] = false; stack 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 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 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 | 深さ優先探索の応用によるノード分類

### 合格

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 void dfs_color(vector vs[], Int colors[], Int n) { bool visited[n]; loop(i,0,n) { visited[i] = false; colors[i] = 0; } stack 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 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; } }