articulation points (http://codeforces.com/contest/732/problem/F), C++ (gcc)

Language: Layout:

#include <bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back

const int N = 4e5 + 5;

vector<int> g[N];

int low[N], dis[N], timer = 0, vis[N] = {0};

int disjoint[N] = {0}, labels[N];

vector<int> bridgeTree[N];
vector<pii> bridgeNode[N];

map<pii, int> bridg;
map<pii, int> id;
vector<pii> edge;

void dfs(int s, int p){
    low[s] = dis[s] = timer++;
    vis[s] = 1;
    
    for(auto i : g[s]){
        if(!vis[i]){
            dfs(i, s);
            low[s] = min(low[s], low[i]);
            if(dis[s] < low[i]){
                //it is a bridge as no node in the subtree of 'i' has a link to the upper nodes.
                bridg[mp(min(i, s), max(i,s))] = 1;
            }
        }
        else if(i != p){
            //it is visited, so, it means that it is a upper node and for upper node we know that 
            //it is yet to be explored (as it is dfs in undirected graph)
            low[s] = min(low[s], dis[i]);
        }
    }
}

void connectedComponents(int s, int lbl){
    labels[s] = lbl;        
    disjoint[lbl]++;
    vis[s] = 1;
    
    for(auto i : g[s])
        if(!vis[i]){
            if(bridg[mp(min(i,s), max(i,s))]) continue;
            connectedComponents(i, lbl);
        }
}

void joinComponent(int s, int p, int lbl){
    vis[s] = 1;
    
    for(auto i : g[s]){
        if(vis[i] == 2 || i == p || bridg[mp(min(i, s), max(i, s))]) continue;
        int idx = id[mp(min(i, s), max(i, s))];
        edge[idx] = mp(s, i);
        if(vis[i] == 0) joinComponent(i, s, lbl);
    }
    vis[s] = 2;
}

void buildTree(int s){
    vis[s] = 1;
    
    for(auto i : g[s]){
        if(vis[i]) continue;
        if(bridg[mp(min(i, s), max(i, s))]){
            bridgeTree[labels[s]].pb(labels[i]), bridgeNode[labels[s]].pb(mp(s, i));
            bridgeTree[labels[i]].pb(labels[s]), bridgeNode[labels[i]].pb(mp(i, s));
        }
        buildTree(i);
    }
}

void bridgeDfs(int s, int p){
    for(int i = 0; i < (int)bridgeTree[s].size(); i++){
        int lbl = bridgeTree[s][i], u = bridgeNode[s][i].first, v = bridgeNode[s][i].second;
        
        if(lbl == p) continue;
        int idx = id[mp(min(u, v), max(u, v))];
        edge[idx] = mp(v, u);
        bridgeDfs(lbl, s);
    }
}

int solve(int n){
    memset(vis, 0, sizeof(vis));
    for(int j = 1; j <= n; j++)
        if(!vis[j]) dfs(j, 0);
        
    int lbl = 1;
    memset(vis, 0, sizeof(vis));
    for(int j = 1; j <= n; j++)
        if(!vis[j]) connectedComponents(j, lbl++);
        
    memset(vis, 0, sizeof(vis));
    for(int j = 1; j <= n; j++)
        if(!vis[j]) joinComponent(j, 0, labels[j]);
        
    int mx = 0, src = -1;
    for(int j = 1; j < lbl; j++)
        if(disjoint[j] > mx) mx = disjoint[j], src = j;
        
    memset(vis, 0, sizeof(vis));
    buildTree(1);
    
    bridgeDfs(src, 0);
    return mx;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    for(int j = 0; j < m; j++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        id[mp(min(u, v), max(u, v))] = j;
        edge.pb(mp(u, v));
    }
    cout << solve(n) << endl;
    
    for(auto i : edge) cout << i.first << " " << i.second << endl;
    return 0;
}

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 1.73 sec, absolute running time: 0.09 sec, cpu time: 0.05 sec, memory peak: 30 Mb, absolute service time: 1,83 sec