find cut-vertices

cut-vertex.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAXN = 100 * 1000;

int mark[MAXN], low[MAXN];
bool visited[MAXN], iscutv[MAXN];
vector<int> alist[MAXN];
int n, m;
int g_counter;
int root_dfs, nadj2root;

void DFS(int u, int parent) 
{
  // if (visited[u]) return;
  if (root_dfs == parent)
    nadj2root++;

  visited[u] = true;
  mark[u] = low[u] = g_counter++;

  for (size_t i = 0; i < alist[u].size(); i++) {
    const int v = alist[u][i];
    if (!visited[v]) {
      DFS(v, u);
      low[u] = min(low[u], low[v]); // update my low
      if (mark[u] <= low[v])        // < bridge, == cycle
        iscutv[u] = true;
    } else { // v is already visited, backward edge
      low[u] = min(low[u], mark[v]);
    }
  }
}

void find_cutv() 
{
  for (int i = 0; i < n; ++i)
    if (!visited[i]) {
      DFS(root_dfs = i, -1);
      // if the root of dfs is a cut-vertex itself
      iscutv[i] = nadj2root > 1;
    }
}

void mainmain() 
{
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    alist[u].push_back(v);
    alist[v].push_back(u);
  }
  find_cutv();

  for (int i = 0; i < n; i++)
    if (iscutv[i])
      cout << i << ' ';
  cout << endl;
}

void clean_slate() 
{
  memset(visited, 0, n * sizeof(visited[0]));
  memset(iscutv, 0, n * sizeof(iscutv[0]));

  nadj2root = 0;
  g_counter = 0;
  for (int i = 0; i < n; i++)
    alist[i].clear();
}

int main() 
{
  int _;
  cin >> _;
  while (_--) {
    mainmain();
    clean_slate();
  }
  return 0;
}