B3610 [图论与代数结构 801] 无向图的块 题解

· · 题解

题目传送门

双倍经验

题意

给定一个图，求点双连通分量数量（按字典序输出）和其中的节点（按从大到小输出）。

割点及点双连通分量的定义

割点的定义

对于一个连通图，如果一个点被删去后，图不连通，则称这个点为割点。

具体的解释可以看下面这张图：

点双连通分量的定义

如果一个连通图内，任意一个点都不是割点，那么称这个连通图为点双连通分量。

具体的解释可以看下面这张图：

题目分析

对于点双连通分量，可以用 Tarjan 算法求解，其中，判断割点的条件为 u != root || son > 1，其中，u 代表需要判断的节点，root 代表根，son 代表子节点数量。

AC 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, M = 2e6 + 10;
int head[N], ver[2 * M], nxt[2 * M], tot = 1;
int n, m, dfn[N], low[N], num, rt;
int dcc, cut[N];     // 边双连通分量数量和是否为割点。
int stk[N], tp;      // 深搜栈和栈顶。
vector<int> DCC[N];  // 边双连通分量。

void addedge(int x, int y) {  // 建边。
  ver[++tot] = y;
  nxt[tot] = head[x];
  head[x] = tot;
}

void tarjan(int u) {  // 求强连通分量。
  dfn[u] = low[u] = ++num;    // 时间戳和回溯值赋值。
  int son = 0;               // 子节点数。
  stk[++tp] = u;              // 入栈
  for (int i = head[u]; i; i = nxt[i]) {  // 遍历子节点。
    int v = ver[i];
    if (!dfn[v]) {  // 没遍历过。
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {  // 满足条件。
        son++;
        if (u != rt || son > 1) cut[u] = 1;  // 满足是割点的条件。
        dcc++;                                // 把遍历到的点加入新的点双连通分量中。
        int z;
        do {
          z = stk[tp--];
          DCC[dcc].push_back(z);
        } while (z != v);
        DCC[dcc].push_back(u);
      }
    } else {
      low[u] = min(low[u], dfn[v]);  // 遍历过则只更新回溯值。
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    if (u == v) continue;  // 自环。
    addedge(u, v);         // 建图。
    addedge(v, u);
  }
  for (int i = 1; i <= n; i++)  // 遍历图。
    if (!dfn[i]) {
      rt = i;
      tarjan(rt);
    }
  for (int i = 1; i <= dcc; i++) {  // 排序。
    sort(DCC[i].begin(), DCC[i].end());
  }
  sort(DCC + 1, DCC + dcc + 1);  // vector 自带比较器。
  printf("%d\n", dcc);           // 输出。
  for (int i = 1; i <= dcc; i++) {
    for (int j = 0; j < DCC[i].size(); j++) {
      printf("%d ", DCC[i][j]);
    }
    puts("");
  }
  return 0;
}