Strong connected components

When a directed graph set S satisfies "for every vertex u and v, exists a path from u to v", this graph could be called an SCC. SCC can be found by applying DFS twice. This is called Kosaraju's algorithm O( V + E ). DFS1 will start from any node that has not yet been searched, and during the DFS1 nodes are pushed into a stack in post-order. DFS2 start from the top of the stack, for every nodes on the top that has not yet been assigned to an SCC, and will DFS through the reversed graph, assigning all nodes it traverses through as the same SCC. It's kind of like to DFS through the graph from each leaf.
Note that if all nodes of the same cycle will be contained in the same SCC, so if we think each group of nodes of an SCC as 1 vertex, there will be no cycles, thus forming a DAG, and DAG is good, because DP can be done on DAG.

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2499
UVA 11504 - Dominos
Basically just find all the SCCs and shrink each of them to a "super node", seeing the whole SCC as 1 node, we can take it as a DAG. The heads of the dominos are the nodes that has 0 in degree ( nothing can make it move ).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;

vector<int> G[MAXN], G2[MAXN];
vector<int> stk;
int scc_cnt, sccno[MAXN], vis[MAXN];
int in[MAXN];
void init(int n){
    for(int i = 0; i < n; ++i) G[i].clear(), G2[i].clear();
    memset( in, 0, sizeof(in) );
}
void dfs1(int u){
    if( vis[u] ) return;
    vis[u] = 1;
    for(int i = 0; i < G[u].size(); ++i) dfs1( G[u][i] );
    stk.push_back( u );
}
void dfs2(int u){
    if( sccno[u] ) return;
    sccno[u] = scc_cnt;
    for(int i = 0; i < G2[u].size(); ++i) dfs2( G2[u][i] );
}
void find_scc(int n){
    scc_cnt = 0;
    memset( sccno, 0, sizeof(sccno) );
    memset( vis, 0, sizeof(vis) );
    stk.clear();
    for(int i = 0; i < n; ++i) dfs1( i );
    for(int i = n - 1; i >= 0; --i)
        if( !sccno[ stk[i] ] )
            ++scc_cnt, dfs2( stk[i] );
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        int n, m; scanf("%d %d", &n, &m);
        init( n );
        while( m-- ){
            int x, y; scanf("%d %d", &x, &y);
            --x, --y;
            G[x].push_back( y );
            G2[y].push_back( x );
        }
        find_scc( n );
        for(int u = 0; u < n; ++u)
            for(int i = 0; i < G[u].size(); ++i){
                int v = G[u][i];
                if( sccno[u] != sccno[v] )
                    ++in[ sccno[v] ];
            }
        int ans = 0;
        for(int i = 1; i <= scc_cnt; ++i)
            if( in[i] == 0 )
                ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2299
UVA 11324 - The Largest Clique
Given a graph, find the largest weak connected component ( for any u, v, exists a path u -> v or v -> u ). This could still be solved by SCC. Shrink SCC components to super nodes and assign nodes with values of their size. Now use DP to find the largest sum value of a path in the new DAG.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;

int scc_cnt, sccno[MAXN], vis[MAXN];
vector<int> G[MAXN], G2[MAXN];
vector<int> stk;
void dfs1(int u){
    if( vis[u] ) return;
    vis[u] = 1;
    for(int i = 0; i < G[u].size(); ++i) dfs1( G[u][i] );
    stk.push_back( u );
}
void dfs2(int u){
    if( sccno[u] ) return;
    sccno[u] = scc_cnt;
    for(int i = 0; i < G2[u].size(); ++i) dfs2( G2[u][i] );
}
void find_scc(int n){
    scc_cnt = 0;
    stk.clear();
    memset( sccno, 0, sizeof(sccno) );
    memset( vis, 0, sizeof(vis) );
    for(int i = 0; i < n; ++i) dfs1( i );
    for(int i = n - 1; i >= 0; --i)
        if( !sccno[ stk[i] ] )
            ++scc_cnt, dfs2( stk[i] );
}

int size[MAXN], adj[MAXN][MAXN];
int memo[MAXN];
int dp(int u){
    int &ans = memo[u];
    if( ans >= 0 ) return ans;
    ans = size[u];
    for(int v = 1; v <= scc_cnt; ++v)
        if( u != v && adj[u][v] )
            ans = max( ans, dp( v ) + size[u] );
    return ans;
}

void solve(int n){
    memset( size, 0, sizeof(size) );
    memset( adj, 0, sizeof(adj) );
    for(int i = 0; i < n; ++i){
        ++size[ sccno[i] ];
        for(int j = 0; j < G[i].size(); ++j)
            adj[ sccno[i] ][ sccno[ G[i][j] ] ] = 1;
    }
    memset( memo, -1, sizeof(memo) );
    int ans = 0;
    for(int i = 1; i <= scc_cnt; ++i) // SCCs might not be connected to each other
        ans = max( ans, dp( i ) );
    printf("%d\n", ans);
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        int n, m; scanf("%d %d", &n, &m);
        for(int i = 0; i < n; ++i) G[i].clear(), G2[i].clear();
        for(int i = 0; i < m; ++i){
            int u, v; scanf("%d %d", &u, &v);
            --u, --v;
            G[u].push_back( v ), G2[v].push_back( u );
        }
        find_scc( n );
        solve( n );        
    }
    return 0;
}

2186 -- Popular Cows
Given some directed edges, find the number of nodes that are reachable from all other nodes.
If an SCC is reachable from all other SCCs, all of the nodes in the SCC are reachable from all other nodes. Again we compress the graph, making SCCs to super nodes. Now we will find that we what matches the requirement is the leaf of the new DAG. However, if there are 2 or more different leaves on this DAG, neither of them will be reachable from each other, thus leading the number of nodes reachable from all other nodes to 0.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e4 + 4;
const int MAXM = 5e4 + 4;

int n, m;
vector<int> G[MAXN], G2[MAXN];

int vis[MAXN];
vector<int> stk;
void dfs1(int u){
    vis[u] = 1;
    for(int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if( !vis[v] ) dfs1( v );
    }
    stk.push_back( u );
}
int scc_cnt, sccno[MAXN];
void dfs2(int u){
    sccno[u] = scc_cnt;
    for(int i = 0; i < G2[u].size(); ++i){
        int v = G2[u][i];
        if( !sccno[v] ) dfs2( v );
    }
}
void find_scc(){
    for(int u = 1; u <= n; ++u) if( !vis[u] )
        dfs1( u );
    for(int i = stk.size() - 1; i >= 0; --i)
        if( !sccno[ stk[i] ] )
            ++scc_cnt, dfs2( stk[i] );
}

int size[MAXN], out[MAXN];
void solve(){
    for(int u = 1; u <= n; ++u){
        ++size[ sccno[u] ];
        for(int i = 0; i < G[u].size(); ++i){
            int v = G[u][i];
            if( sccno[u] != sccno[v] ) ++out[ sccno[u] ];
        }
    }
    int out0_sccno = -1, ok = 1;
    for(int i = 1; i <= scc_cnt; ++i)
        if( out[i] == 0 ){
            if( out0_sccno != -1 ){
                ok = 0;
                break;
            } else
                out0_sccno = i;
        }
    if( ok && out0_sccno != -1 ) printf("%d\n", size[ out0_sccno ]);
    else puts("0");
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i){
        int a, b; scanf("%d %d", &a, &b);
        G[a].push_back( b );
        G2[b].push_back( a );
    }
    find_scc();
    solve();
    return 0;
}