阅读量:1
无向图
- 割点：删除x和与x相连的边，图不再连通，x为割点
- 割边：删去该边e，图不再连通，e为割边
- 点双连通分量：其本身不存在割点，但可以有原图的割点（此时在这个点双中就是普通的点），极大图，一个点双中可以有多个原图的割点
- 边双连通分量：其本身不存在割边，极大图
- 点双不具有传递性，边双具有传递性((x,y),(y,z)=>(x,z))
Tarjan
- 时间戳dfn：访问到的时间
- 返祖边：搜索树上连向其祖先节点的边
- 由于搜索树结构，不存在横向边（连向同层节点的边）
- low[u]定义：u和以u为根的子树通过返祖边（包括树边和非树边）能连到的最小的dfn
- 若是一条树边：low[u]=min(low[v[,low[u])
- 若是一条非树边：low[u]=min(low[u],dfn[v])
求割点
- 割点满足：其儿子的low[v]>=dfn[u]，即没有儿子跨过u，儿子与u相连只有树边
- 对于根要判断儿子个数大于1
- 可以走反向边
- 特判为根且搜索树上只有一个儿子，此时注意重边
- 求a,b间的割点，tarjan(a)判断如下
if(low[v]>=dfn[x]){ if(x!=a&&x!=b&&dfn[x]<=low[b])ge[x]=true; }
求点双
- 每次访问到一个点将其入栈
- 若满足low[v]>=dfn[u]，则出栈直到v出，此时出栈的所有点和v是一个点双
- 每个点双，每个点都在一个环上，若点双有奇环，则所有点都在奇环
- 判奇环，二分图黑白染色
求割边
- 割边满足： 一条边只走一次，v没有另一条边到达u（父亲）即low[v]>dfn[u]
- 可以避免重边
求边双
- 一边只走一次，若low[u]==dfn[u]（除了树边，没有其他到树上祖先的边），则为边双
点双缩点连图
- 割点单独为一个点，每个点双除割点，缩成一个点
- 割点向其所在的点双连边
边双缩点连图
- 每个边双缩点，用桥相连
缩点连图
- 转为无向无环图
有向图
- 强连通：图中存在路径u--->v和v--->u
- 弱连通：图中只存在路径u--->v或v--->u
- 强连通分量：该子图中对于任意一点对，存在路径u--->v和v--->u，极大图
Tarjan
- 时间戳dfn
- low[u]为u和以u为根的子树中能连到的还未出栈的最小dfn
- 访问到则入栈
- dfn[u]=low[u]，即到该点往上不会有强连通（有向边），
- 出栈直到u出栈，此时出栈的点为一个强连通分量
强连通缩点
- 将有向图，转为有向无环图
- 之后可以考虑入度出度，topu排序dp
- 注意会有重边，所以缩点连边时要判断是否已经连上，不要重复计算入度出度
- 求加入最少的边变成一个强连通，先缩点
int a=0,b=0; for(int i=1;i<=cc;++i){ if(!in[i])a++; if(!out[i])b++; } if(cc==1)std::cout<<0<<std::endl; else std::cout<<max(a,b)<<std::endl;
代码
- 割点
auto tarjan=[&](auto &&tarjan,int x)->void{ dfn[x]=low[x]=++tt;int ch=0; for(auto v:G[x]){ if(!dfn[v]){ tarjan(tarjan,v); low[x]=min(low[x],low[v]); if(low[v]>=dfn[x]){ ch++; if(x1!=rt||ch>1) ge[x]=true; } }else low[x]=min(low[x],dfn[v]); } if(rt==x&&ch==1)ge[x]=false; }; - 点双，缩点
std::vector<int> dfn(n+5,0),low(n+5,0);int tt=0; std::vector<int> sz(n+5,0),col(n+5,0);int cc=0; std::stack<int> st;std::vector<std::vector<int>> hs(n+5); std::vector<bool> ge(n+5,false);int rt=0; auto tarjan=[&](auto &&tarjan,int x)->void{ dfn[x]=low[x]=++tt;int ch=0; st.push(x); for(auto v:G[x]){ if(!dfn[v]){ tarjan(tarjan,v); low[x]=min(low[x],low[v]); if(low[v]>=dfn[x]){ ch++; if(x!=rt||ch>1){ ge[x]=true; } int y;cc++;//缩点 do{ y=st.top();st.pop(); col[y]=cc;sz[cc]++;hs[cc].push_back(y); }while(y!=v); hs[cc].push_back(x);sz[cc]++;//割点放入 } }else low[x]=min(low[x],dfn[v]); } }; for(int i=1;i<=n;++i)if(!dfn[i]){ rt=i; tarjan(tarjan,i); } - 割边，边双，缩点
std::vector<int> dfn(n+5,0),low(n+5,0);int tt=0; std::vector<int> sz(n+5,0),col(n+5,0);int cc=0; std::stack<int> st;std::vector<std::vector<int>> hs(n+5); auto tarjan=[&](auto &&tarjan,int x,int p)->void{ dfn[x]=low[x]=++tt; st.push(x); for(auto [v,i]:G[x]){//i为边的编号 if(i==p)continue; if(!dfn[v]){ tarjan(tarjan,v,i); low[x]=min(low[x],low[v]); // if(low[v]>dfn[x]){ // std::cout<<i<<std::endl; // } }else low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]){ int y;cc++; do{ y=st.top();st.pop(); col[y]=cc;sz[cc]++;hs[cc].push_back(y); }while(y!=x); } }; for(int i=1;i<=n;++i)if(!dfn[i])tarjan(tarjan,i,0); - 强连通分量
std::vector<int> dfn(n+5,0),low(n+5);int tt=0; std::stack<int> st;std::vector<std::vector<int>> hs(n+5); std::vector<int> col(n+5,0),sz(n+5,0);int cc=0; auto tarjan=[&](auto &&tarjan,int x)->void{ dfn[x]=low[x]=++tt; st.push(x); for(auto v:G[x]){ if(!dfn[v]){ tarjan(tarjan,v); low[x]=min(low[x],low[v]); }else if(!col[v])low[x]=min(low[x],dfn[v]); } if(dfn[x]==low[x]){ ++cc; int y; do{ y=st.top();st.pop(); col[y]=cc;sz[cc]++;hs[cc].push_back(y); }while(y!=x); } }; for(int i=1;i<=n;++i){ if(!dfn[i])tarjan(tarjan,i); }
