3648번: 아이돌

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

#include<stdio.h>
#include<vector>
#define pb(x) push_back(x);
using namespace std;
const int MAX_N = 1000;
int n, m, c[MAX_N * 2 + 1];
vector<int> adj[2][MAX_N * 2 + 1];
bool ck[MAX_N * 2 + 1];
vector<int> vis, tvis;
void dfs(int h, bool type) {
    if (ck[h] != type) return;
    ck[h] = !type;
    for (auto t : adj[type][h])
        dfs(t, type);
    vis.pb(h);
}
int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        for (int i = 0; i <= 2 * n; i++)
            adj[0][i].clear(), adj[1][i].clear();
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            adj[0][n - a].pb(n + b);
            adj[0][n - b].pb(n + a);
            adj[1][n + b].pb(n - a);
            adj[1][n + a].pb(n - b);
        }
        adj[0][n - 1].pb(n + 1);
        adj[1][n + 1].pb(n - 1);
        vis.clear();
        for (int i = 0; i < n; i++)
            dfs(i, false), dfs(i + n + 1, false);
        tvis = vis;
        for (int i = tvis.size() - 1; i >= 0; i--) {
            if (!ck[tvis[i]]) continue;
            vis.clear();
            dfs(tvis[i], true);
            for (auto it : vis) c[it] = i;
        }
        bool res = true;
        for (int i = 0; i < n; i++)
            res &= c[i] != c[2 * n - i];
        puts(res ? "yes" : "no");
    }
    return 0;
}