Strongly Connected Components

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct TarjanSCC {
5
    int n;
6
    vector<vector<int>> g;
7
    vector<int> idx, low, comp, st;
8
    vector<char> onstack;
9
    int timer = 0, comp_cnt = 0;
10
11
    TarjanSCC(int n): n(n), g(n), idx(n, -1), low(n, -1), comp(n, -1), onstack(n, 0) {}
12
13
    void add_edge(int u, int v) { g[u].push_back(v); }
14
15
    void dfs(int u) {
16
        idx[u] = low[u] = timer++;
17
        st.push_back(u);
18
        onstack[u] = 1;
19
        for (int v : g[u]) {
20
            if (idx[v] == -1) { // tree edge
21
                dfs(v);
22
                low[u] = min(low[u], low[v]);
23
            } else if (onstack[v]) { // back edge to a node on stack
24
                low[u] = min(low[u], idx[v]);
25
            }
26
        }
27
        // If u is a root of an SCC, pop the stack up to u
28
        if (low[u] == idx[u]) {
29
            while (true) {
30
                int v = st.back(); st.pop_back();
31
                onstack[v] = 0;
32
                comp[v] = comp_cnt; // assign component id
33
                if (v == u) break;
34
            }
35
            comp_cnt++;
36
        }
37
    }
38
39
    // Returns number of components and fills comp[u] with [0..comp_cnt-1]
40
    int run() {
41
        for (int u = 0; u < n; ++u) if (idx[u] == -1) dfs(u);
42
        return comp_cnt;
43
    }
44
};
45
46
int main() {
47
    ios::sync_with_stdio(false);
48
    cin.tie(nullptr);
49
50
    int n, m; // vertices 0..n-1
51
    if (!(cin >> n >> m)) return 0;
52
    TarjanSCC scc(n);
53
    for (int i = 0; i < m; ++i) {
54
        int u, v; cin >> u >> v; // assume 0-based input
55
        scc.add_edge(u, v);
56
    }
57
    int k = scc.run();
58
59
    cout << k << "\n";
60
    for (int u = 0; u < n; ++u) cout << scc.comp[u] << (u+1==n?'\n':' ');
61
}
62

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    int n, m; // 0..n-1
9
    if (!(cin >> n >> m)) return 0;
10
    vector<vector<int>> g(n), gt(n);
11
    for (int i = 0; i < m; ++i) {
12
        int u, v; cin >> u >> v; // 0-based
13
        g[u].push_back(v);
14
        gt[v].push_back(u); // transpose edge
15
    }
16
17
    vector<int> vis(n, 0), order; order.reserve(n);
18
    // First pass: compute finishing order on original graph
19
    function<void(int)> dfs1 = [&](int u) {
20
        vis[u] = 1;
21
        for (int v : g[u]) if (!vis[v]) dfs1(v);
22
        order.push_back(u); // push on finish
23
    };
24
    for (int u = 0; u < n; ++u) if (!vis[u]) dfs1(u);
25
26
    // Second pass: explore transpose in reverse finishing order
27
    vector<int> comp(n, -1);
28
    int cid = 0;
29
    function<void(int)> dfs2 = [&](int u) {
30
        comp[u] = cid;
31
        for (int v : gt[u]) if (comp[v] == -1) dfs2(v);
32
    };
33
34
    for (int i = n - 1; i >= 0; --i) {
35
        int u = order[i];
36
        if (comp[u] == -1) {
37
            dfs2(u);
38
            ++cid;
39
        }
40
    }
41
42
    cout << cid << "\n";
43
    for (int u = 0; u < n; ++u) cout << comp[u] << (u+1==n?'\n':' ');
44
    return 0;
45
}
46

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Reuse Tarjan to get SCCs, then build condensation and count sources/sinks.
5
struct TarjanSCC {
6
    int n; vector<vector<int>> g; vector<int> idx, low, comp, st; vector<char> on;
7
    int timer = 0, cc = 0;
8
    TarjanSCC(int n): n(n), g(n), idx(n,-1), low(n,-1), comp(n,-1), on(n,0) {}
9
    void add_edge(int u,int v){ g[u].push_back(v);}    
10
    void dfs(int u){
11
        idx[u]=low[u]=timer++; st.push_back(u); on[u]=1;
12
        for(int v:g[u]){
13
            if(idx[v]==-1){ dfs(v); low[u]=min(low[u],low[v]); }
14
            else if(on[v]) low[u]=min(low[u],idx[v]);
15
        }
16
        if(low[u]==idx[u]){
17
            while(true){ int v=st.back(); st.pop_back(); on[v]=0; comp[v]=cc; if(v==u) break; }
18
            cc++;
19
        }
20
    }
21
    int run(){ for(int i=0;i<n;++i) if(idx[i]==-1) dfs(i); return cc; }
22
};
23
24
int main(){
25
    ios::sync_with_stdio(false);
26
    cin.tie(nullptr);
27
28
    int n,m; if(!(cin>>n>>m)) return 0;
29
    TarjanSCC scc(n);
30
    for(int i=0;i<m;++i){ int u,v;cin>>u>>v; scc.add_edge(u,v);}    
31
    int k=scc.run();
32
33
    if(k==1){ cout<<0<<"\n"; return 0; }
34
35
    vector<int> indeg(k,0), outdeg(k,0);
36
    // Build condensation degrees without storing full DAG
37
    for(int u=0;u<n;++u){
38
        for(int v: scc.g[u]){
39
            int cu = scc.comp[u], cv = scc.comp[v];
40
            if(cu!=cv){
41
                outdeg[cu]++;
42
                indeg[cv]++;
43
            }
44
        }
45
    }
46
47
    int sources=0,sinks=0;
48
    for(int c=0;c<k;++c){ if(indeg[c]==0) sources++; if(outdeg[c]==0) sinks++; }
49
50
    cout << max(sources, sinks) << "\n";
51
    return 0;
52
}
53

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct SCC {
5
    int n; vector<vector<int>> g, gt; vector<int> comp, vis, order;
6
    SCC(int n): n(n), g(n), gt(n), comp(n,-1), vis(n,0) {}
7
    void add_edge(int u,int v){ g[u].push_back(v); gt[v].push_back(u);} // u -> v, and v -> u in transpose
8
    void dfs1(int u){ vis[u]=1; for(int v:g[u]) if(!vis[v]) dfs1(v); order.push_back(u);}    
9
    void dfs2(int u,int c){ comp[u]=c; for(int v:gt[u]) if(comp[v]==-1) dfs2(v,c);}    
10
    int run(){ for(int i=0;i<n;++i) if(!vis[i]) dfs1(i); int c=0; for(int i=n-1;i>=0;--i){ int u=order[i]; if(comp[u]==-1) dfs2(u,c++);} return c; }
11
};
12
13
// 2-SAT over variables x in [0..vars-1]
14
struct TwoSAT {
15
    int vars; // number of boolean variables
16
    SCC scc;  // implication graph with 2*vars nodes (x and not x)
17
    TwoSAT(int n): vars(n), scc(2*n) {}
18
    // Map literal to node id: x -> 2*x,  ~x -> 2*x^1
19
    static int var(int x){ return 2*x; }
20
    static int neg(int id){ return id^1; }
21
    static int lit(int x, bool val){ return 2*x ^ (val?0:1); } // val=true => x, false => ~x
22
23
    // add implication a -> b
24
    void imply(int a, int b){ scc.add_edge(a,b); }
25
26
    // add clause (A or B), where A and B are literal ids
27
    void add_or(int A, int B){ imply(neg(A), B); imply(neg(B), A); }
28
29
    // force literal A to be true
30
    void add_true(int A){ imply(neg(A), A); }
31
32
    // enforce A == B
33
    void add_equiv(int A, int B){ add_or(A, B); add_or(neg(A), neg(B)); }
34
35
    // enforce A -> B
36
    void add_if(int A, int B){ imply(A, B); imply(neg(B), neg(A)); }
37
38
    // Solve: returns pair<is_satisfiable, assignment>
39
    pair<bool, vector<int>> solve(){
40
        scc.run();
41
        vector<int> assign(vars, 0);
42
        for(int x=0;x<vars;++x){
43
            int a = var(x), na = neg(a);
44
            if(scc.comp[a] == scc.comp[na]) return {false, {}}; // contradiction
45
        }
46
        // Variables with higher component order (later in topo) are false by this scheme
47
        vector<pair<int,int>> ord(2*vars);
48
        for(int i=0;i<2*vars;++i) ord[i] = {scc.comp[i], i};
49
        sort(ord.rbegin(), ord.rend());
50
        vector<int> val(2*vars, -1);
51
        for(auto [c, id] : ord){ if(val[id]==-1){ val[id]=0; val[neg(id)]=1; } }
52
        for(int x=0;x<vars;++x) assign[x] = val[var(x)];
53
        return {true, assign};
54
    }
55
};
56
57
int main(){
58
    ios::sync_with_stdio(false);
59
    cin.tie(nullptr);
60
61
    int nVars, m; // variables, clauses of form (a v b). Input format example:
62
    // First line: nVars m
63
    // Next m lines: ax av bx bv  where literal is (x if av=1 else ~x)
64
    if(!(cin>>nVars>>m)) return 0;
65
    TwoSAT solver(nVars);
66
    for(int i=0;i<m;++i){
67
        int ax,av,bx,bv; cin>>ax>>av>>bx>>bv;
68
        int A = TwoSAT::lit(ax, av==1);
69
        int B = TwoSAT::lit(bx, bv==1);
70
        solver.add_or(A, B);
71
    }
72
    auto [ok, asg] = solver.solve();
73
    if(!ok){ cout << "UNSAT" << '\n'; }
74
    else{
75
        cout << "SAT" << '\n';
76
        for(int i=0;i<nVars;++i) cout << asg[i] << (i+1==nVars?'\n':' ');
77
    }
78
    return 0;
79
}
80