Undirected Graph - Find bridges, articulation vertices, and contract cycles in graph

undirected.cc

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define MAXN    1000+1
#define MAXE    2*10000

int N;

int E;
int v[MAXE];
int start[MAXN];
int nexte[MAXE];

bool visited[MAXN];
int enterT[MAXN];
int lowT[MAXN];
int DFSTime;
int root;
int rootC;

void dfs(int x, int parent) {
    visited[x] = true;
    enterT[x] = lowT[x] = DFSTime; ++ DFSTime;
    for (int i = start[x]; i != -1; i = nexte[i]) {
        if (!visited[v[i]]) {
            if (x == root) ++ rootC;
            dfs(v[i], x);
            lowT[x] = min(lowT[x], lowT[v[i]]);
        }
        else if (v[i] != parent)
            lowT[x] = min(lowT[x], enterT[v[i]]);
    }
}

vector<int> articulation_vertex() {
    vector<int> vertices;
    if (rootC > 1) vertices.push_back(root);
    for (int u = 1; u <= N; ++ u) {
        if (u == root) continue;
        for (int i = start[u]; i != -1; i = nexte[i])
            if (lowT[v[i]] >= enterT[u]) {
                vertices.push_back(u);
                break;
            }
    }
    return vertices;
}

vector< pair<int, int> > bridge() {
    vector< pair<int, int> > edges;
    for (int u = 1; u <= N; ++ u)
        for (int i = start[u]; i != -1; i = nexte[i])
            if (lowT[v[i]] > enterT[u])
                edges.push_back(make_pair(u, v[i]));
    return edges;
}

int Color[MAXN];
int colors;

void ContractGraph() {
    memset(Color, -1, sizeof(Color));
    colors = 0; Color[root] = colors;

    queue<int> Q; Q.push(root);
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (int i = start[x]; i != -1; i = nexte[i]) {
            if (Color[v[i]] != -1) continue;
            if (lowT[v[i]] > enterT[x])
                Color[v[i]] = ++ colors;
            else
                Color[v[i]] = Color[x];
            Q.push(v[i]);
        }
    }

    for (int i = 1; i <= N; ++ i)
        printf("color(%d) = %d\n", i, Color[i]);
}

// input a connected graph
int main() {
    int M;
    E = 0;
    memset(start, -1, sizeof(start));

    scanf("%d%d", &N, &M);
    while (M --) {
        int x, y;
        scanf("%d%d", &x, &y);
        v[E] = y; nexte[E] = start[x]; start[x] = E; ++ E;
        v[E] = x; nexte[E] = start[y]; start[y] = E; ++ E;
    }

    DFSTime = 0;
    root = 1; rootC = 0;
    memset(visited, false, sizeof(visited));
    dfs(root, -1);

    vector<int> vertices = articulation_vertex();
    vector< pair<int, int> > edges = bridge();

    printf("articulation vertices\n");
    for (int i = 0; i < vertices.size(); ++ i)
        printf("%d\n", vertices[i]);
    printf("bridges\n");
    for (int i = 0; i < edges.size(); ++ i)
        printf("%d %d\n", edges[i].first, edges[i].second);

    ContractGraph();
    return 0;
}