无向图的割点（tarjan）

割点&＃xff1a;删除有向图某个点及其对应的邻边会使得联通分量数量增多&＃xff0c;这个点称为割点。在求割点使用到了Tarjan算法。
同求有向图的强连通分量类似&＃xff0c;都是使用到了dfn以及low数组用来标记搜索树的状态。但有所区别的是&＃xff0c;在深搜的时候要区别根的情况以及非根结点&＃xff0c;如果是根只要有两个或两个以上的子树分支这个肯定是割点&＃xff1b;而对于非根结点如果$dfn[u]>\&＃61;low[v]$时&＃xff0c;显然就有这个u为割点&＃xff0c;为什么呢&＃xff1f;因为这个条件说明这个搜索分支的子树最多只会搜到我这个父节点&＃xff0c;搜不到更早的deep了&＃xff0c;那么它要回到更早的那一部分有且仅有经过这个点的一条路那么这个点一定时割点。

Code&＃xff1a;

#include
using namespace std;/*** luogu P3388
*/struct Edge {int to;int next;
};Edge E[1000005];
int head[200005], cnt;
int dfn[200005], low[200005], deep;
set<int> ans;
int n, m;void edge_add(int u, int v) {E[cnt].to &＃61; v;E[cnt].next &＃61; head[u];head[u] &＃61; cnt&＃43;&＃43;;
}void init() {memset(dfn, 0, sizeof(dfn));memset(head, -1, sizeof(head));cnt &＃61; deep &＃61; 0;ans.clear();int u, v;for (int i &＃61; 0; i < m; i&＃43;&＃43;) {cin >> u >> v;edge_add(u, v);edge_add(v, u);}
}void tarjan(int u, int rt) {int rtnum &＃61; 0;dfn[u] &＃61; low[u] &＃61; &＃43;&＃43;deep;for (int cur &＃61; head[u]; ~cur; cur &＃61; E[cur].next) {int v &＃61; E[cur].to;if (!dfn[v]) {tarjan(v, rt);low[u] &＃61; min(low[u], low[v]);//表示子树无法回到u前面//若判桥此处条件是low[v] > dfn[u]if (u !&＃61; rt && dfn[u] <&＃61; low[v])ans.insert(u);if (rt &＃61;&＃61; u)rtnum&＃43;&＃43;;} elselow[u] &＃61; min(low[u], dfn[v]); //由于有向图是双边 防止用low会更新到压根不会访问到的根位置}if (u &＃61;&＃61; rt && rtnum >&＃61; 2)ans.insert(rt);
}int main() {
// freopen("E:\\Visual_Studio_Code_File\\C_Cpp\\input.in", "r", stdin);
// freopen("E:\\Visual_Studio_Code_File\\C_Cpp\\output.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0);cin >> n >> m;init();for (int u &＃61; 1; u <&＃61; n; u&＃43;&＃43;)if (!dfn[u])tarjan(u, u);cout << ans.size() << endl;for (set<int>::iterator it &＃61; ans.begin(); it !&＃61; ans.end(); it&＃43;&＃43;) {cout << *it << " ";}cout << endl;return 0;
}