백준 23741번 야바위 게임

문제 링크

한 간선을 여러 번 탈 수 있다. 그렇다고 해서 진짜 여러 번 타면 시간초과를 받는다.

해당 정점에 홀수 번 이동해서 도착했는지, 짝수 번 이동해서 도착했는지만 기록한다. 2번 움직여서 도달한 정점은 무조건 4번, 6번 움직여서 도달할 수 있기 때문이다. 그냥 간선 하나 잡고 와리가리 하면 되니까.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

int N, M, X, Y;
vector<vector<int>> adj;
bool visited[2][1001];

void dfs(int cur, int cnt) {
    visited[cnt % 2][cur] = true;
    for (auto next : adj[cur]) {
        if (visited[(cnt+1) % 2][next]) continue;
        dfs(next, cnt+1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> X >> Y;

    adj.resize(N+1);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }

    if (adj[X].empty()) {
        cout << -1;
        return 0;
    }

    dfs(X, 0);

    vector<int> ans;
    for (int i = 1; i <= N; i++) {
        if (visited[Y%2][i]) ans.emplace_back(i);
    }
    for (auto x : ans) {
        cout << x << ' ';
    }

    return 0;
}