Submission #1130151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130151		gyg	Povjerenstvo (COI22_povjerenstvo)	C++20	100 / 100	775 ms	149220 KiB

Main

/*
Note that no directed odd cycles iff each SCC is (undirectedly) bipartite. 

    Proof:
    1) If there is a directed odd cycle, there must an undirected odd cycle, so not bipartite.
    2) If there is a non-bipartite graph, there must be an undirected odd cycle. We can show that there must also be 
       a directed odd cycle. 
       For some undirected odd cycle u --- v pick some direction. For each edge w --> x that does not point in that 
       direction, there must be an odd path pointing in the opposite direction x ->- w. This is because x must be able 
       to reach w, and it must be an odd path so that the cycle along with the edge is even. 
       Thus, we can "correct" all edges and reveal and directed cycle.

Consider applying the subtask 2 solution to each SCC as separate graphs, in particular in reverse topological order. 
The first SCC will be complete so we don't have to worry about any node having no out-edges. As in subtask 2, two colour
it and label all nodes of one colour as in, making all nodes going into them out. 

Note that the whole SCC will be labelled in or out, and also parts of other SCCs may be labelled out. However, we don't
have to worry about those nodes ever again (their condition of looking at an in node is satisfied) and can just ignore 
them in future. 

Subsequent SCCs may not be complete, though they will necessarily still be bipartite. Thus, run the entire subtask 2 
solution on them - first greedily include nodes with no out-edges and exclude nodes into them, then run two colouring 
and arbitrarily include nodes of a colour.

Takeaway: 
Condition on whole graph (especially involving cycles) simplifies to condition on each SCC.
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 5e5 + 5;

int n, m;
arr<vec<int>, N> in, out;

arr<bool, N> tp_vs;
vec<int> tp;
void tp_dfs(int u) {
    tp_vs[u] = true;
    for (int v : out[u])
        if (!tp_vs[v]) tp_dfs(v);
    tp.push_back(u);
}
int nm_sccs;
arr<int, N> scc;
arr<vec<int>, N> scc_nds;
void scc_dfs(int u) {
    scc[u] = nm_sccs, scc_nds[nm_sccs].push_back(u);
    for (int v : in[u])
        if (!scc[v]) scc_dfs(v);
}
void prcmp() {
    for (int u = 1; u <= n; u++)
        if (!tp_vs[u]) tp_dfs(u);
    reverse(tp.begin(), tp.end());

    for (int u : tp) 
        if (!scc[u]) nm_sccs++, scc_dfs(u);

    // for (int i = 1; i <= nm_sccs; i++) {
    //     cout << i << ": ";
    //     for (int u : scc_nds[i]) cout << u << " ";
    //     cout << endl;
    // }
}

arr<int, N> typ, cnt;
set<pii> ord;
void intl(int id) {
    ord.clear();
    for (int u : scc_nds[id]) {
        if (typ[u] != 0) continue;
        for (int v : out[u])
            cnt[u] += (typ[v] == 0);
        ord.insert({cnt[u], u});
    }
}
void rmv(int u) {
    if (!ord.count({cnt[u], u})) return;
    ord.erase({cnt[u], u});
    for (int v : in[u]) {
        if (!ord.count({cnt[v], v})) continue;
        ord.erase({cnt[v], v});
        cnt[v]--;
        ord.insert({cnt[v], v});
    }
}
arr<int, N> cl;
void cl_dfs(int u) {
    for (int v : out[u]) {
        if (cl[v] || scc[v] != scc[u]) continue;
        cl[v] = (cl[u] == 1) ? 2 : 1;
        cl_dfs(v);
    }
}
void slv(int id) {
    intl(id);
    while (ord.size() && ord.begin()->fir == 0) {
        int u = ord.begin()->sec;
        ord.erase(ord.begin());
        typ[u] = 1, rmv(u);
        for (int v : in[u])
            typ[v] = 2, rmv(v);
    }

    cl[scc_nds[id][0]] = 1, cl_dfs(scc_nds[id][0]);
    for (int u : scc_nds[id]) {
        if (typ[u] != 0) continue;
        if (cl[u] != 1) continue;
        typ[u] = 1;
        for (int v : in[u]) typ[v] = 2;
    }
}

void cmp() {
    for (int i = nm_sccs; i >= 1; i--) 
        slv(i);

    vec<int> ans;
    for (int u = 1; u <= n; u++) {
        assert(typ[u] != 0);
        if (typ[u] == 1) ans.push_back(u);        
    }
    cout << ans.size() << endl;
    for (int u : ans) cout << u << " ";
    cout << endl;
}

signed main() {
    // freopen("a.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        out[u].push_back(v), in[v].push_back(u);
    }

    prcmp();
    cmp();
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33