inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u,int in_edge){
dfn[u]=low[u]=++timeclock;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){//搜索树上v是u的子节点
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])bridge[i]=bridge[i^1]=1;//标记是否是桥边
}
else if(i!=(in_edge^1)){//无向边(u,v)不在搜索树上
low[u]=min(low[u],dfn[v]);
}
}
}
int main(){
n=read();m=read();tot=1;//注意这个tot的初始值是1不是0
for(int i=1;i<=m;++i){
a[i]=read();b[i]=read();
add(a[i],b[i]);add(b[i],a[i]);
}
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
...
return 0;
}
inline void tarjan(int x){
dfn[x]=low[x]=++timeclock;
int child=0;//记录子节点数量
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
child++;
if(x!=root||child>=2)cut[x]=1;//标记x是割点
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
...
for(int i=1;i<=n;i++)
if(!dfn[i])root=i,tarjan(i);
...
}
inline void dfs(int x){
belong[x]=dcc;//编号为x的节点属于第dcc个边双连通分量
for(int i=head[x];i;i;=nxt[i]){
int y=to[i];
if(belong[y]||bridge[i])continue;
//如果点y已经遍历过 或者 (x,y)之间的边是桥边,则跳过
dfs(y);
}
}
int main(){
...
for(int i=1;i<=n;++i)
if(!belong[i]){//划分每个点属于哪个边双连通分量
++dcc;
dfs(i);
}
...
}
inline void tarjan(int x){
dfn[x]=low[x]=++tim;st[++top]=x;
if (x==root&&head[x]==0){
dcc[++cnt].push_back[x];
return;
}
int flag=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1)cut[x]=true;
cnt++;int z;
do{
z=st[top--];
dcc[cnt].push_back[z];
}while(z!=y)
dcc[cnt].push_back[x];
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
...
for(int i=1;i<=cnt;i++)
for(int j=0;j<dcc[i].size();j++)
printf("%d", dcc[i][j]);
...
}
num=cnt;
//cnt表示的是图中v-DCC的个数
for(int i=1;i<=n;++i)
if(cut[i])new_id[i]=++num;
//给每个割点一个新的编号,从cnt+1开始
tot_c=1;
//重新建图的边的总数,从1开始的技巧不说了
for(int i=1;i<=cnt;++i)
for(int j=0;j<dcc[i].size();++j){
int x=dcc[i][j];
if(cut[x]){//在割点和包含它的v-DCC之间连边
add_c(i,new_id[x]);
add_c(new_id[x],i);
}
else belong[x]=i;//割点之外的点,只会属于一个v-DCC
}
void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
void tarjan(int u){
dfn[u]=low[u]=++timeclock;
st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!color[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){//满足强连通分量的条件
color[u]=++cnt;
while(st[top]!=u){
color[st[top]]=cnt;
top--;
}
top--;
}
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int a,b;
a=read();b=read();
add(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
//至于最后输出什么,就看题目求什么了;
//总之,我们已经得到了强连通分量的个数cnt
//每个点分别属于哪个强连通分量(color数组记录)
return 0;
}
for(int x=1;x<=n;++x)
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(color[x]==color[y])continue;
add_c(color[x],color[y]);
//如果这条有向边的两个端点不属于同一个强连通分量
//则在这两个强连通分量之间连边,边的方向保持不变
}
原文:https://www.cnblogs.com/PPXppx/p/11590709.html