bridges.cpp

// Finds bridges and cut vertices
// Receives:
// N: number of vertices
// l: adjacency list
// Gives:
// vis, seen, par (used to find cut vertices)
// ap - 1 if it is a cut vertex, 0 otherwise
// brid - vector of pairs containing the bridges
typedef pair<int, int> PII;

int N;
vector<int> l[MAX];
vector<PII> brid;
int vis[MAX], seen[MAX], par[MAX], ap[MAX];
int cnt, root;

void dfs(int x) {
  if (vis[x] != -1)
    return;
  vis[x] = seen[x] = cnt++;

  int adj = 0;
  for (int i = 0; i < (int)l[x].size(); i++) {
    int v = l[x][i];
    if (par[x] == v)
      continue;
    if (vis[v] == -1) {
      adj++;
      par[v] = x;
      dfs(v);
      seen[x] = min(seen[x], seen[v]);
      if (seen[v] >= vis[x] && x != root)
        ap[x] = 1;
      if (seen[v] == vis[v])
        brid.push_back(make_pair(v, x));
    } else {
      seen[x] = min(seen[x], vis[v]);
      seen[v] = min(seen[x], seen[v]);
    }
  }
  if (x == root)
    ap[x] = (adj > 1);
}

void bridges() {
  brid.clear();
  for (int i = 0; i < N; i++) {
    vis[i] = seen[i] = par[i] = -1;
    ap[i] = 0;
  }
  cnt = 0;
  for (int i = 0; i < N; i++)
    if (vis[i] == -1) {
      root = i;
      dfs(i);
    }
}