[16168] 퍼레이드

https://www.acmicpc.net/problem/16168

16168번: 퍼레이드

연결그래프이면서, 홀수간선을 갖는 정점이 2개 이하인지를 판별해야 한다.

bfs로 아무거나 시작점으로 잡아서 v개를 방문했는지를 체크하고,

입력을 인접리스트로 받으면 1&adj[i].size()로 홀수간선을 갖는지를 파악할 수 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

vector<int> adj[3001];

queue<int> q;

int v, e;

bool vst[3001];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> v >> e;

    int i;

    for (i = 0; i < e; i++) {

        int X, Y;

        cin >> X >> Y;

        adj[X].push_back(Y);

        adj[Y].push_back(X);

    }

    q.push(1);

    vst[1] = true;

    int chk = 1;

    while (!q.empty()) {

        int cur = q.front();

        q.pop();

        for (auto& nxt : adj[cur]) {

            if (vst[nxt] == false) {

                vst[nxt] = true;

                q.push(nxt);

                chk++;

            }

        }

    }

    if (chk != v) {

        cout << "NO";

        return 0;

    }

    int cnt = 0;

    for (i = 1; i <= v and cnt <= 2; i++) {

        int S = adj[i].size();

        if (S & 1) cnt++;

    }

    cout << (cnt <= 2 ? "YES" : "NO");

    return 0;

}

---