有向图

• 强连通：有向图节点两两可达，则此图为强连通
• 强连通分量（Strong Connected Components，SCC）：极大强连通子图

无向图

• 割边：无向图删掉一条边后，连通分量变大，则称该边为割边或桥。
• 割点：无向图删掉一条边后，连通分量变大，则称该边为割点或割顶。
• 边双连通分量：极大不包含割边的连通块
• 点双连通分量：极大不包含割点的连通块

时间戳dfn(u) 节点u第一次被访问的次序编号;

追溯值low(u) 节点u能够追溯到的最早的时间戳;

有向图强连通分量 SCC缩点

const int MX=10010;
vector<int> g[MX]; 
int dfn[MX],low[MX],tot; 
int stk[MX],instk[MX],top;
int scc[MX],siz[MX],cnt;

// scc[i] = 0， i是单独一个点

void tarjan(int x){
    //入x时，盖戳、入栈
    dfn[x] = low[x] = ++tot;
    stk[++top] = x,instk[x] = 1;
    for(int y : g[x]){
        if (!dfn[y]) {//若y尚未访问
            tarjan(y);
            low[x] = min(low[x],low[y]);//回x时更新low
        } else if(instk[y]) {//若y已访问且在栈中
            low[x] = min(low[x],dfn[y]);//在x时更新low
        }
    }
    //离x时，收集SCC
    if(dfn[x]==low[x]){//若x是SCC的根
        int y; ++cnt;
        do {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;//SCC编号
            ++siz[cnt];//SCC大小
        } while(y != x);
    }
}
/*
int n, m;
cin >> n >> m;
for (int i=0; i<m; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
}
for (int i=1; i<=n; i++) {
    if (!dfn[i]) tarjan(i);
}
for(int x=1; x<=n; x++) // 缩点
    for(int y : g[x])
	      if(scc[x]!=scc[y]) {
				     //...
	      }
*/

• P3387 【模板】缩点

无向图割点

x为割点，x移除后会让连通分量增加。

• x非根节点，且存在子节点y满足$low[y]\ge dfn[x]$，此时y子树中没有其他路径通往x的祖先
• x为根节点，且存在至少两个子节点。

// p3388 logu
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dfn[N], low[N], idx;
vector<int> g[N];
set<int> cut;
int n, m;
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++idx;
	int child = 0;
	for (auto v : g[u]) {
		if (!dfn[v]) { //未访问过才是树边
			child++; // 树边连接的点才是子节点
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u] && fa != -1) cut.insert(u);
		}
		else low[u] = min(low[u], dfn[v]); // 返祖边更新
	}
	if (child >= 2 && fa == -1) cut.insert(u);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1);

	cout << cut.size() << "\\n";
	for (auto x : cut) cout << x << " ";
    cout << "\\n";
}