11498번: Odd Cycle

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

#include<cstdio>
#include<vector>
using namespace std;
int tc, n, m, ck[100001], valid[100001], cl[100001], flag[100001];
vector<int> adj[2][100001], vis;
void dfs(int h, int ty) {
    if (ck[h] ^ ty) return;
    ck[h] = !ty;
    for (auto &it : adj[ty][h]) dfs(it, ty);
    vis.push_back(h);
}
vector<int> via, via2;
bool dfs3(int h) {
    if (flag[h]) {
        int i = 0;
        while (via[i] ^ h) i++;
        printf("1\n%d\n", via2.size() + via.size() - i);
        for (auto &it : via2) printf("%d\n", it);
        for (; i < via.size(); i++) printf("%d\n", via[i]);
        return true;
    }
    int tt = valid[h];
    valid[h] = -1;
    via2.push_back(h);
    for (auto &it : adj[0][h]) if (valid[it] == tt && cl[it] - cl[h] & 1) {
        if (dfs3(it)) return true;
    }
    via2.pop_back();
    return false;
}
bool dfs2(int h) {
    via.push_back(h);
    flag[h] = 1;
    for (auto &it : adj[0][h]) if (valid[it] == valid[h]) {
        if (!~cl[it]) {
            cl[it] = cl[h] + 1;
            if (dfs2(it)) return true;
        }
        else if (cl[h] + 1 - cl[it] & 1) {
            via2.clear();
            dfs3(it);
            return true;
        }
    }
    via.pop_back();
    flag[h] = 0;
    return false;
}
int main() {
    for (scanf("%d", &tc); tc--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            adj[0][i].clear();
            adj[1][i].clear();
            valid[i] = cl[i] = -1;
            ck[i] = 0;
        }
        for (int i = 0, x, y; i < m; i++) {
            scanf("%d%d", &x, &y);
            adj[0][x].push_back(y);
            adj[1][y].push_back(x);
        }
        vis.clear();
        for (int i = 1; i <= n; i++) dfs(i, 0);
        vector<int> tvis = vis;
        int rr = 0;
        for (int i = n; i--;) if (ck[tvis[i]]) {
            vis.clear();
            dfs(tvis[i], 1);
            for (auto &it : vis) valid[it] = i, flag[it] = 0;
            cl[vis[0]] = 0;
            via.clear();
            if (dfs2(vis[0])) { rr = 1; break; }
        }
        if (!rr) puts("-1");
    }
    return 0;
}