割点与桥
算法简介
如果无向图中删除某个点$u$，连通块数量增加，则$u$为图的一个割点；本算法用来找到图中所有割点；如果删除无向图的一条边 $e$，连通块数量增加，则称 $e$ 为桥。
算法思想
利用时间戳概念在图中建立一个DFS树，用$dfn$数组存储每个点的时间戳，用$low$数组存储每个点能到达的最远的祖先，如果存在一个儿子节点$v$使得$low[v] \geq low[u]$，则$u$为割点。总时间复杂度为：$O(n)$。如果 $low[v]> dfn[u]$，则连接 u, v 的边为桥。
注意：dfs的第一个节点，如果只有一个儿子则不是割点，否则一定是一个割点。
强连通分量
算法简介
该算法主要处理有向图的强连通分量问题。对于有向图中的一个强连通分量 (Strongly Connected Component，一个集合中的点相互可达) 可以看做一个点，这样有向图就构成一个DAG，更便于处理问题。
算法思想
对一个图进行dfs，形成一棵dfs树，用dfn表示该点的时间戳，用low存储该点在dfs树中能到达的最远的祖先的时间戳，找到每个scc的第一个点。把每个点访问的点入栈，找到scc的第一个点时将栈中该点后的所有点倒出形成一个集合。
scc的第一个点满足一个性质：$low[i]=dfn[i]$。利用这个性质可以轻松找到该点，在dfs要时刻记得更新low值。对于i，如果连接的点未遍历过，则遍历该点，回溯时用儿子节点更新i的low:$low[i]=min(low[son(i)],low[i])$。如果连接的点遍历过并且还未形成集合:$low[i]=min(low[i],dfn[u])$。整个过程的时间复杂度为$O(N)$。
注意：如果连接的点已经成环，则无法利用该点更新low值！
dfs完毕后，枚举每个点并枚举旧图的边并连接新图的边，注意打一些标记，不要连成自环、重边。时间复杂度为$O(M)$。
总时间复杂度为线性。
代码
#include<stack>
int n,cnt,scc_cnt,dfn[2020],low[2020],scc[2020];
bool vis[2020];
//dfn表示时间戳，low表示能到达的最小祖先，scc表示新集合的编号
//用结构体表示两个图
struct MAP{
int e,be[2020],to[maxx],ne[maxx],d[maxx];
MAP(){e=0;}
void init(){
For(i,0,e) to[i]=ne[i]=0;
For(i,0,n) be[i]=d[i]=0;
e=0;
}
void add(int x,int y){
to[++e]=y;
ne[e]=be[x];
be[x]=e;
d[y]++;
}
}New,Old;
//初始化
void init(){
ans=cnt=scc_cnt=0;
For(i,0,n){
dfn[i]=low[i]=scc[i]=vis[i]=0;
c[i]=oo;
}
Old.init(); New.init();
}
//tarjan
stack<int>s;
void tarjan(int id){
s.push(id);
dfn[id]=low[id]=++cnt;
for(int i=Old.be[id];i;i=Old.ne[i]){
int go=Old.to[i];
if(!dfn[go]){
tarjan(go);
low[id]=min(low[id],low[go]);
}
else if(!scc[go]) low[id]=min(low[id],dfn[go]);
}
if(low[id]==dfn[id]){
scc_cnt++;
while(1){
int x=s.top(); s.pop();
scc[x]=scc_cnt;
if(x==id) break;
}
}
}
//建新图
void build(){
For(id,1,n){
vis[scc[id]]=1;
for(int i=Old.be[id];i;i=Old.ne[i]){
int go=Old.to[i];
if(!vis[scc[go]]){
New.add(scc[id],scc[go]);
vis[scc[go]]=1;
}
}
for(int i=Old.be[id];i;i=Old.ne[i]) vis[Old.to[i]]=0;
vis[scc[id]]=0;
}
}
int main()
{
init();
For(i,1,n) if(!dfn[i]) tarjan(i);
build();
return 0;
}双连通分量
算法简介
默认为无向图
点双连通分量：子图上任意两点存在至少两条不存在公共节点的路径，也可以说是不存在割点的子图
边双连通分量：子图上任意两点存在至少两条不存在公共边的路径，也可以说是不存咋割边的子图
点双连通分量与边双连通分量的异同：
同：两者都是一个环
异：可以用下图直接解释，整个图是一个边双连通分量，但不是点双连通分量，因为点3是一个割点。1,2,3是点双与边双，3,4,5也是点双与边双，但是合在一起1,2,3,4,5只是一个边双，即边双连通分量具有传递性，而点双连通分量不具有传递性。
算法思想
边双连通分量类似强分量算法类似处理即可。
点双连通分量：开一个栈将边压入，当一个点判定为割点时，将栈中所有边弹出，这些边连接成一个点双连通分量。（注意代码中，弹栈的位置）
代码
对一个连通图，输出割点，割边，点双连通个数，点双连通分量最多的边数
题目链接：http://121.48.165.90/contest/170/problem/J
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int N = 2022;
int n, m, cnt, num, mx, cut_edge, cut_node, dfn[N], low[N], edge_num[N], sz[N];
vector<int> edge[N];
stack<pair<int, int>> st;
void dfs(int id, int fa){
dfn[id] = low[id] = ++cnt;
bool if_cut_node = 0;
int son = 0;
for(auto u : edge[id]){
if(u == fa) continue;
bool if_cut_edge = 0;
if(!dfn[u]){
++son;
st.push(make_pair(id, u));
dfs(u, id);
low[id] = min(low[id], low[u]);
if(low[u] >= dfn[id]){
if_cut_node = 1;
++num;
int tmp = 0;
while(1){
pair<int, int> e = st.top(); st.pop();
mx = max(mx, ++tmp);
if(e.first == id && e.second == u) break;
}
}
if(low[u] > dfn[id]) if_cut_edge = 1;
}
else if(dfn[u] < dfn[id]){
st.push(make_pair(id, u));
low[id] = min(low[id], dfn[u]);
}
if(if_cut_edge) ++cut_edge;
}
if(!fa) cut_node += (son > 1);
else if(if_cut_node){ ++cut_node; }//cout << id << endl; }
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
cin >> n >> m;
for(int i = 1, u, v; i <= m; ++i){
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i = 1; i <= n; ++i)
if(!dfn[i]) dfs(i, 0);
cout << cut_node << " " << cut_edge << " " << num << " " << mx;
return 0;
}
