0w1

Biconnected Components

A vertex biconnected component (bcc) can be defined as a connected component (cc) that is still a cc after any vertex is plucked out of the graph, and usually we would think about the bcc as the largest component that satisfies. An edge bcc has a similar definition, except that it is another way to say that there is no bridge in a cc, compared to saying that there is no cut in a cc, where that would be a vertex bcc.

Tarjan's algorithm O( V + E ) is one of the most desirable way to implement bcc assigining for each vertex on a graph. However as fast implementations for bridge bcc are too complex for me, I do it in a more straightforward method, but costs higher constant factors ( about 3x slower ).

First we do it with the simplest Tarjan's algorithm, assigning each vertex's visit value ( pre ) as we dfs along while making sure we never run back to it's direct father. Updating the low value ( the highest ancestor vertex it could reach without the current edge connecting ), checking whether u is a cut ( lowv >= pre[u] ), or u <-> v is a bridge ( lowv == pre[v] <=> lowv > pre[u] ). So far it is easy to catch, but to separate bcc and assign each vertex, I prefer performing another floodfill after the whole simple Tarjan's algorithm, avoiding the bridges we've marked with each BFS.

However, vertex bcc cannot be solved this way, because you wouldn't know which cut should belong to which bcc. We have to implement with a stack to simulate the process.
1. Initialize an empty stack S, and set all nodes as "unvisited"
2. Choose any node as the root to start Tarjan's algorithm
3. Let the current node be u, visit each v that shares an edge with u:
a. if v is father of u, discard this visit
b. push edge( u, v ) to S
c. if v is visited before, take it as an back edge to update low[u]
d. otherwise recursively apply Tarjan's algorithm
e. update lowu by lowv
f . if u is cut <=> lowv >= pre[u], pop out edges from S until ( u, v ) is out, and these edges will form a bcc

POJ3352 -- Road Construction

Here's a simple problem to check my code with floodfill. The problem is to find how many more bidirectional edges are required to newly build on the given component ( all edges are bidirectional ). It is easy to observe that we need to find all the bridge bccs and shrink each bcc into a vertex. By applying this change we could transform the graph to a tree. Now find the number of vertices with only 1 degree, those are the leaves of the graph. At last greedily, we would find that the answer is ( leaf_count + 1 ) / 2.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e3 + 3;
const int MAXM = 5e3 + 3;

int n, m;
vector<int> G[MAXN];
int dfs_clock;
int pre[MAXN], low[MAXN];
map<pii, bool> is_bridge;

int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    for(int v: G[u]){
        if( v == fa ) continue;
        if( !pre[v] ){
            int lowv = dfs( v, u );
            lowu = min( lowu, lowv );
            if( lowv == pre[v] )
                is_bridge[ pii( u, v ) ] = is_bridge[ pii( v, u ) ] = true;
        } else if( pre[v] < pre[u] ) // back edge
            lowu = min( lowu, pre[v] );
    }
    return low[u] = lowu;
}

int bccno[MAXN], bcc_cnt, fvis[MAXN];
void floodfill(int _u, int col){
    queue<int> q; q.push( _u );
    while( !q.empty() ){
        int u = q.front(); q.pop();
        bccno[u] = bcc_cnt;
        fvis[u] = 1;
        for(int v: G[u]) if( !fvis[v] )
            if( !is_bridge.count( pii( u, v ) ) )
                q.push( v );
    }
}
void tarjan(int n){
    dfs_clock = 0;
    memset( pre, 0, sizeof(pre) );
    memset( low, 0, sizeof(low) );
    is_bridge.clear();
    dfs( 1, -1 );
    bcc_cnt = 0;
    memset( fvis, 0, sizeof(fvis) );
    for(int i = 1; i <= n; ++i) if( !fvis[i] )
        floodfill( i, bcc_cnt++ );
}

int deg[MAXN];
void solve(){
    memset( deg, 0, sizeof(deg) );
    for(int u = 1; u <= n; ++u)
        for(int v: G[u]){
            int bu = bccno[u], bv = bccno[v];
            if( bu != bv ) ++deg[bu], ++deg[bv];
        }
    int leaf_cnt = 0;
    for(int i = 1; i <= bcc_cnt; ++i)
        if( deg[i] == 2 )
            ++leaf_cnt;
    printf("%d\n", ( leaf_cnt + 1 ) / 2);
}

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

UVa Online Judge
Given that some person i cannot sit next to some person j, output the number of people that can never be in any odd number cycles ( >= 3 ) formed by these people.
For n is rather small, ( 1 <= n <= 1000 ), we can build bidirectional edges for people that do not hate each other. We now would have to find the number of nodes that aren't on any odd cycles. Now consider connected components, we could find that nodes on a same odd cycle should be contained in the same vertex bcc. Noticing that whether a component is bipartite contradicts with the existence of any odd cycle, and figuring out that if a bcc contains an odd cycle we could have any others in the same bcc join the cycle, we will know that we are to find all the bcc that are not bipartite.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e3 + 3;
const int MAXM = 1e6 + 6;

int dfs_clock, bcc_cnt;
vector<int> es[MAXN], bcc[MAXN]; // bcc starts from 1
int pre[MAXN], low[MAXN], is_cut[MAXN], bccno[MAXN];
stack<pii> stk;
int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < es[u].size(); ++i){
        int v = es[u][i];
        if( v == fa ) continue;
        if( !pre[v] ){
            ++child;
            stk.push( pii( u, v ) );
            int lowv = dfs( v, u );
            if( lowv >= pre[u] ){
                is_cut[u] = 1;
                bcc[ ++bcc_cnt ].clear();
                for(;;){
                    int nu = stk.top().first, nv = stk.top().second;
                    stk.pop();
                    if( bccno[nu] != bcc_cnt ){
                        bcc[bcc_cnt].push_back( nu );
                        bccno[nu] = bcc_cnt;
                    }
                    if( bccno[nv] != bcc_cnt ){
                        bcc[bcc_cnt].push_back( nv );
                        bccno[nv] = bcc_cnt;
                    }
                    if( nu == u && nv == v ) break;
                }
            }
            lowu = min( lowu, lowv );
        } else if( pre[v] < pre[u] ){
            stk.push( pii( u, v ) );
            lowu = min( lowu, pre[v] );
        }
    }
    if( fa < 0 && child == 1 ) is_cut[u] = 0;
    return low[u] = lowu;
}
void find_bcc(int n){
    dfs_clock = bcc_cnt = 0;
    for(int i = 0; i < n; ++i) bcc[i].clear();
    memset( pre, 0, sizeof(pre) );
    memset( low, 0, sizeof(low) );
    memset( is_cut, 0, sizeof(is_cut) );
    memset( bccno, 0, sizeof(bccno) );
    for(int i = 0; i < n; ++i) if( !pre[i] )
        dfs( i, -1 );
}

int hate[MAXN][MAXN];

int col[MAXN], odd[MAXN];
bool bipart(int u, int b){
    for(int i = 0; i < es[u].size(); ++i){
        int v = es[u][i];
        if( bccno[v] != b ) continue;
        if( col[v] == col[u] ) return false;
        if( !col[v] ){
            col[v] = 3 - col[u];
            if( !bipart( v, b ) ) return false;
        }
    }
    return true;
}

int main(){
    int n, m;
    while( scanf("%d %d", &n, &m) == 2 && n + m ){
        memset( hate, 0, sizeof(hate) );
        for(int i = 0; i < m; ++i){
            int a, b; scanf("%d %d", &a, &b);
            --a, --b;
            hate[a][b] = hate[b][a] = 1;
        }
        for(int i = 0; i < n; ++i) es[i].clear();
        for(int i = 0; i < n; ++i)
            for(int j = i + 1; j < n; ++j) if( !hate[i][j] ){
                es[i].push_back( j );
                es[j].push_back( i );
            }
        find_bcc( n );
        memset( odd, 0, sizeof(odd) );
        for(int i = 1; i <= bcc_cnt; ++i){
            memset( col, 0, sizeof(col) );
            for(int j = 0; j < bcc[i].size(); ++j) bccno[ bcc[i][j] ] = i;
            int u = bcc[i][0];
            col[u] = 1;
            if( !bipart( u, i ) )
                for(int j = 0; j < bcc[i].size(); ++j)
                    odd[ bcc[i][j] ] = 1;
        }
        int ans = n;
        for(int i = 0; i < n; ++i) if( odd[i] )
            --ans;
        printf("%d\n", ans);
    }
    return 0;
}