首先我是一个傻逼，我不会强连通分量。??
点双连通分量
定义：不包含割点的连通块。
做法：还是考虑 Tarjan，首先思考怎么求割点，我从 \(u\) 开始找其他连通块，发现我这个连通块要是不能从其他边上到 \(u\) 上面那么 \(u\) 一定是割点，因为割掉后就不跟上面联通了，但是发现这个不适用于根节点，根节点要是连出去两个连通块就肯定是割点。
很抽象，不如直接看代码：
#include<cstdio>
#include<iostream>
#include<vector>
#define eb emplace_back
namespace IO{
template<typename T> inline void rd(T &x){
x=0;bool f=0;char c=0;
while(c<'0'||c>'9') f|=c=='-',c=getchar();
while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
x=f?-x:x;
}
template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
template<typename T> inline void wt(char c,T x){
int stk[114],top=0;
if(x<0) x=-x,putchar('-');
do stk[++top]=x%10,x/=10; while(x);
while(top) putchar(stk[top--]+'0');
putchar(c);
}
template<typename T,typename ...Args> inline void wt(char c,T x,Args ...args){wt(c,x),wt(c,args...);}
template<typename T,typename ...Args> inline void wt(char s,char c,T x,Args ...args){wt(c,x),wt(c,args...),putchar(s);}
};
using namespace IO;
using namespace std;
const int N=5e5+7;
int n,m;
vector<int>g[N];
int dfn[N],low[N],t;
int stk[N],top;
vector<int>p[N]; int tot;
inline void tarjan(int u,int fa){
dfn[u]=low[u]=++t;
stk[++top]=u;
for(int v:g[u]){
if(v==fa) continue;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
++tot;
int y;
do{
y=stk[top--];
p[tot].eb(y);
}while(y!=v);
p[tot].eb(u);
}
}
else low[u]=min(low[u],dfn[v]);
}
if(!fa&&!g[u].size()) p[++tot].eb(u);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
rd(n,m);
while(m--){
int u,v; rd(u,v);
if(u==v) continue;
g[u].eb(v),g[v].eb(u);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
wt('\n',tot);
for(int i=1;i<=tot;i++){
wt(' ',p[i].size());
for(int x:p[i]) wt(' ',x);
puts("");
}
return 0;
}
边双连通分量
定义：不包含桥的连通块。
做法：不难发现如果一条边是桥说明下面那个点永远到不了和上面一样高度的点，所以跟上面类似的判就好了。
至于怎么输出，将所有割边断掉后直接输出连通块就好了。
说的还是很抽象，不如代码：
#include<cstdio>
#include<iostream>
#include<vector>
#define eb emplace_back
namespace IO{
template<typename T> inline void rd(T &x){
x=0;bool f=0;char c=0;
while(c<'0'||c>'9') f|=c=='-',c=getchar();
while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
x=f?-x:x;
}
template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
template<typename T> inline void wt(char c,T x){
int stk[114],top=0;
if(x<0) x=-x,putchar('-');
do stk[++top]=x%10,x/=10; while(x);
while(top) putchar(stk[top--]+'0');
putchar(c);
}
template<typename T,typename ...Args> inline void wt(char c,T x,Args ...args){wt(c,x),wt(c,args...);}
template<typename T,typename ...Args> inline void wt(char s,char c,T x,Args ...args){wt(c,x),wt(c,args...),putchar(s);}
};
using namespace IO;
using namespace std;
const int N=5e5+7,M=4e6+7;
int n,m;
int e[M],ne[M],h[N],idx;
int dfn[N],low[N],t;
int stk[N],top;
vector<int>p[N]; int tot;
bool flag[M],st[N];
inline void init(int n){ for(int i=1;i<=n;i++) h[i]=-1; }
inline void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; }
inline void tarjan(int u,int from){
dfn[u]=low[u]=++t;
stk[++top]=u;
for(int i=h[u];i!=-1;i=ne[i]){
if(i==(from^1)) continue;
int v=e[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]) flag[i]=flag[i^1]=1;
}
else low[u]=min(low[u],dfn[v]);
}
}
inline void find(int u){
p[tot].eb(u),st[u]=1;
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i];
if(flag[i]||st[v]) continue;
find(v);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
rd(n,m);
init(n);
while(m--){
int u,v; rd(u,v);
if(u==v) continue;
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
// for(int i=0;i<idx;i++) cerr<<flag[i]<<" \n"[i==idx-1];
for(int i=1;i<=n;i++) if(!st[i]) ++tot,find(i);
wt('\n',tot);
for(int i=1;i<=tot;i++){
wt(' ',p[i].size());
for(int x:p[i]) wt(' ',x);
puts("");
}
return 0;
}
仙人掌???
仙人掌用圆方树⚪□?
边仙人掌
定义：每个边至多属于一个简单环的图。
如何建出圆方树？
边仙人掌 虽然我下面画的图是点仙人掌
对于图上的每一个环，我们建一个方点，然后让他与环上的所有点连边。
大概就是这样：
建完就长成这样：
其实就是把每个点双拉出来建图。
我们可以给新的红边设上符合题意的边权，这个通过题目来看，比较抽象，不如直接看下面的题。
代码怎么实现呢？就是上面说的，把每个点双拉出来建菊花图。
int fa[N],fw[N],sum[N];// fa:搜索树上的父亲，fw:搜索树上与父亲相连的边权，sum:圆点表示圆上的点到与搜索树上第一个搜索到的环上的点的距离，方点表示环长
inline void calc(int u,int v,int w){// 一个从 u 到 v 的环，其中 v 向 u 连边的权值为 w
int all=w,now=v;
while(now!=fa[u]) sum[now]=all,all+=fw[now],now=fa[now]; // 求出 sum
sum[++tot]=sum[u],now=v;
while(now!=fa[u]){
int val=min(sum[now],sum[tot]-sum[now]);
g[now].eb(tot,val),g[tot].eb(now,val); // 求出所有点到 u 的距离
now=fa[now];
}
}
inline void tarjan(int u,int FA){
dfn[u]=low[u]=++t;
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i];
if(v==FA) continue;
if(!dfn[v]){
fa[v]=u,fw[v]=w[i];
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
if(low[v]>dfn[u]) g[u].eb(v,w[i]),g[v].eb(u,w[i]); // 加上所有非环边
}
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i];
if(fa[v]==u||dfn[v]<=dfn[u]) continue;
calc(u,v,w[i]); // 找到所有环
}
}
洛谷 P5236 【模板】静态仙人掌
这个题是边仙人掌，现在要求求出两点之间最短路，我们考虑普通的树我们是怎么求两点间距离的，是 \(dep_u+dep_v-2\cdot dep_{lca(u,v)}\)，我们考虑还是用这个，但是不能直接做?，因为方点圆点之间连的边长度不一定是一，那么是什么呢，不难发现就是从当前点走到环上和祖先节点相连的点的最短距离，好像很抽象，不如看图。?
还是上面那张图，注意这玩意是要固定根节点的，不然就没有什么祖先一说了，我设黄点为根节点，图就是这样的（环上的边权都是写在边的顺时针方向，我这里默认原图边权全是 \(1\)）：
这样构建完了就可以做了?？
好像还是不行，如果我的 \(lca\) 是一个方点那就求错了，不过这个也好整，我们再预处理一个环上两点间距离就可以了。
这样就做完了！?
code:
#include<cstdio>
#include<iostream>
#include<vector>
#define eb emplace_back
namespace IO{
template<typename T> inline void rd(T &x){
x=0;bool f=0;char c=0;
while(c<'0'||c>'9') f|=c=='-',c=getchar();
while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
x=f?-x:x;
}
template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
template<typename T> inline void wt(char c,T x){
int stk[114],top=0;
if(x<0) x=-x,putchar('-');
do stk[++top]=x%10,x/=10; while(x);
while(top) putchar(stk[top--]+'0');
putchar(c);
}
template<typename T,typename ...Args> inline void wt(char c,T x,Args ...args){wt(c,x),wt(c,args...);}
template<typename T,typename ...Args> inline void wt(char s,char c,T x,Args ...args){wt(c,x),wt(c,args...),putchar(s);}
};
using namespace IO;
using namespace std;
typedef pair<int,int> PII;
const int N=2e4+7,M=4e4+7,Log=15;
int n,m,q,tot;
int w[M],e[M],ne[M],h[N],idx;
vector<PII>g[N];
int dfn[N],low[N],t;
inline void init(int n){ for(int i=1;i<=n;i++) h[i]=-1; }
inline void add(int a,int b,int c){ w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; }
int fa[N],fw[N],sum[N];
inline void calc(int u,int v,int w){
int all=w,now=v;
while(now!=fa[u]) sum[now]=all,all+=fw[now],now=fa[now];
sum[++tot]=sum[u],now=v;
while(now!=fa[u]){
int val=min(sum[now],sum[tot]-sum[now]);
g[now].eb(tot,val),g[tot].eb(now,val);
now=fa[now];
}
}
inline void tarjan(int u,int FA){
dfn[u]=low[u]=++t;
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i];
if(v==FA) continue;
if(!dfn[v]){
fa[v]=u,fw[v]=w[i];
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
if(low[v]>dfn[u]) g[u].eb(v,w[i]),g[v].eb(u,w[i]);
}
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i];
if(fa[v]==u||dfn[v]<=dfn[u]) continue;
calc(u,v,w[i]);
}
}
int f[N][Log],dep[N],dis[N];
inline void dfs(int u,int fa){
f[u][0]=fa,dep[u]=dep[fa]+1;
for(int j=1;j<Log;j++) f[u][j]=f[f[u][j-1]][j-1];
for(PII A:g[u]){
int v=A.first,w=A.second;
if(v==fa) continue;
dis[v]=dis[u]+w;
dfs(v,u);
}
}
inline PII lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int j=Log-1;j>=0;j--){
if(dep[f[u][j]]>=dep[v]) u=f[u][j];
}
if(u==v) return {0,v};
for(int j=Log-1;j>=0;j--){
if(f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j];
}
return {u,v};
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
rd(n,m,q),tot=n;
init(n);
while(m--){
int u,v,c; rd(u,v,c);
add(u,v,c),add(v,u,c);
}
dep[0]=-1;
tarjan(1,0),dfs(1,0);
while(q--){
int u,v; rd(u,v);
PII son=lca(u,v); int anc=son.first?f[son.first][0]:son.second;
if(anc<=n) wt('\n',dis[u]+dis[v]-2*dis[anc]);
else wt('\n',dis[u]+dis[v]-dis[son.first]-dis[son.second]+min(abs(sum[son.second]-sum[son.first]),sum[anc]-abs(sum[son.second]-sum[son.first])));
}
return 0;
}
点仙人掌
定义：每个点至多属于一个简单环的图。（你发现如果一张图是一个点仙人掌那么他就一定是一个边仙人掌。）