AOJ

# # 目次

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

### # 時間制限超過


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 | 深さ優先探索の応用によるノード分類

### # 合格


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;
}
}


リモートフリーランス。ウェブサービス、スマホアプリエンジニア。

お仕事のご依頼・お問い合わせはこちら