【模板】割点（割边）Tarjan

一.割点

 P3388 【模板】割点（割顶） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 其实跟强连通分量的Tarjan不太一样，但是基本思路还是差不多的。

首先，什么是割点：

在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point）。

其次，什么情况下一个点会是割点：

1. 求根节点的是否为割点，只要其有两棵或两棵以上子树，则为割点。

2. 叶节点都不是割点，所以只剩下要求非叶节点，若一非叶节点的子树的节点没有指向该点的祖先节点的回边，说明删除该点之后，该点的祖先节点与该点的子树不再连通，则说明该节点为割点。

 第一点很好实现，只需要判断一个节点由两个子树即可。麻烦在第二点，也就是判断一个非叶节点的子节点没有超过根节点的回边，什么意思？也就是1->2->3->4。这条路径，以2为父节点，子节点3没有回到超过2的节点的回边。而这个可以用Tarjan算法判断，定义一个记录dfs顺序的dfn数组，和一个记录最早能回到的编号的数组low。

当子节点v最早可以回溯到超过父节点u的时候，也就是low[v]<dfn[u]的时候则断开这个父节点，其他节点仍然可以由他的子节点通过所以当

low[v]>=dfn[u]

时断开u，其他节点则无法通过子节点，形成断路，此时u为割点

#include <bits/stdc++.h>
#include<iostream>
#include<thread>
using namespace std;
#pragma warning(disable:4996);
#define ll signed long long
#define	int ll
#define rep(j,b,e) for(register int j=b;j<=e;j++)
#define drep(j,e,b) for(register int j=(e);j>=(b);j--)
int T = 1;
const int N = 5e5 + 10;
const int mod = 10000;
int n, m, k, q;

template <class T, class ...Arg>
void inline pln(T t, Arg ...args);//打印一行参数
template<typename T>
void inline pln(vector<T> a, string s = " ");
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args);//输入一行数据

//--------------------------------------

vector<int>gra[N];
vector<int>ans(N);
vector<int>pre(N);
vector<int>dfn(N), low(N);
vector<int>stk, inStk(N);
int Time = 0;
void Tarjan(int now, int f) {//f表示当前判断节点作为根节点
	dfn[now] = low[now] = ++Time;
	stk.push_back(now);
	inStk[now] = 1;
	int sonSum = 0;//子树总数
	for (auto nx : gra[now]) {
		if (dfn[nx] == 0) {
			Tarjan(nx, f);
			low[now] = min(low[now], low[nx]);
			if (low[nx] >= dfn[now] && now != f)ans[now] = 1;//子节点最多只能回到now
			if (now == f)sonSum++;//记录子树的数量
		}
		else if (dfn[nx]) {
			low[now] = min(low[now], dfn[nx]);
		}
	}

	if (sonSum >= 2 && now == f)//根节点的子树大于等于2
		ans[now] = 1;
}
int vis[N] = { 0 };
signed main()
{
#ifndef ONLINE_JUDGE
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
	inln(n, m);
	rep(j, 1, m) {
		int f, t;
		inln(f, t);
		gra[f].push_back(t);
		gra[t].push_back(f);
	}
	rep(j, 1, n) {
		if (dfn[j] == 0)
			Tarjan(j, j);
	}
	pln(count(ans.begin() + 1, ans.begin() + 1 + n, 1));
	rep(j, 1, n)
		if (ans[j])
			cout << j << " ";
	return 0;
}

//--------------------------------------
void inline  inln() {}
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args) {
	cin >> t;
	inln(args...);
}
void inline pln() {
	cout << "\n";
}
template <class T, class ...Arg>
void inline pln(T t, Arg ...args) {
	cout << t << " ";
	pln(args...);
}
template<typename T>
void inline pln(vector<T> a, string s) {
	for (T& x : a) {
		cout << x << s;
	}
	cout << endl;
}

二.割边 

P1656 炸铁路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

割边则表示删去此边，剩下的图将无法连通。将low[v] >= num[u]改为low[v] > num[u]，说明子节点甚至不能往回。因为这句代码代表该点的子节点在不经过其父亲节点回不到该点及该点的祖先的，所以u->v这条边是一条割边。

注意无向图的割边要特判重边，防止子节点往回走到根节点然后误判了low

#include <bits/stdc++.h>
#include<iostream>
#include<thread>
using namespace std;
#pragma warning(disable:4996);
#define ll signed long long
#define	int ll
#define rep(j,b,e) for(register int j=b;j<=e;j++)
#define drep(j,e,b) for(register int j=(e);j>=(b);j--)
int T = 1;
const int N = 5e5 + 10;
const int mod = 10000;
int n, m, k, q;

template <class T, class ...Arg>
void inline pln(T t, Arg ...args);//打印一行参数
template<typename T>
void inline pln(vector<T> a, string s = " ");
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args);//输入一行数据
//--------------------------------------
vector<int>gra[N];
vector<int>pre(N);
vector<int>dfn(N), low(N);
int Time = 0;
struct edge {
	int f, t;
};
vector<edge>ans;
void Tarjan(int now, int f) {//f表示当前判断节点作为根节点
	dfn[now] = low[now] = ++Time;

	for (auto nx : gra[now]) {
		if (dfn[nx] == 0) {
			Tarjan(nx, now);
			low[now] = min(low[now], low[nx]);
			if (low[nx] > dfn[now]) {
				ans.push_back({ min(now,nx),max(now,nx) });
			}
		}
		else if (dfn[nx] && nx != f) {//重复直接连边特判
			low[now] = min(low[now], dfn[nx]);
		}
	}
}
int vis[N] = { 0 };
signed main()
{
#ifndef ONLINE_JUDGE
	//freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	inln(n, m);
	rep(j, 1, m) {
		int f, t;
		inln(f, t);
		gra[f].push_back(t);
		gra[t].push_back(f);
	}
	rep(j, 1, n) {
		if (dfn[j] == 0)
			Tarjan(j, j);
	}
	sort(ans.begin(), ans.end(), [](edge a, edge b) {
		if (a.f != b.f)
			return a.f < b.f;
		else
			return a.t < b.t;
		});
	for (auto [f, t] : ans) {
		pln(f, t);
	}
	return 0;
}

//--------------------------------------
void inline  inln() {}
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args) {
	cin >> t;
	inln(args...);
}
void inline pln() {
	cout << "\n";
}
template <class T, class ...Arg>
void inline pln(T t, Arg ...args) {
	cout << t << " ";
	pln(args...);
}
template<typename T>
void inline pln(vector<T> a, string s) {
	for (T& x : a) {
		cout << x << s;
	}
	cout << endl;
}