\(tarjan\)
Robert Tarjan，计算机科学家，以LCA、强连通分量等算法闻名，同时他还参与了开发斐波那契堆、伸展树的工作。
\(Tarjan\)算法是基于深度优先搜索的算法，用于求解图的连通性问题。
缩点
to be continue~
namespace tarjan{
int stk[N],tp; //stack
int dfn[N],low[N],id; //时间戳，最早出现的祖先， 编号
int cg[N],col; //color
int w[N],val[N]; //点权，缩点之后的点权
bool vs[N]; //是否在栈中
il void dfs(int u){
stk[++tp]=u;
vs[u]=1;
dfn[u]=low[u]=++id;
for(ri int i=he[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v);
low[u]=min(low[u],low[e[i].v]);
}
else if(vs[e[i].v]){
low[u]=min(low[u],dfn[e[i].v]);
}
}
if(dfn[u]==low[u]){
col++;
while(stk[tp+1]!=u){
cg[stk[tp]]=col;
val[col]+=w[stk[tp]];
vs[stk[tp--]]=0;
}
}
return;
}
} using namespace tarjan;
code
#include<bits/stdc++.h>
#define ri register
#define cs const
#define il inline
cs int N=1e5+5;
using namespace std;
namespace edge{
int he[N],ho[N],ct;
struct qwq{
int u,v,nxt;
}e[N],o[N];
il void adde(int u,int v,int id){
e[id]=(qwq){u,v,he[u]},he[u]=id;
}
il void addo(int u,int v){
o[++ct]=(qwq){u,v,ho[u]},ho[u]=ct;
}
} using namespace edge;
namespace tarjan{
int stk[N],tp; //stack
int dfn[N],low[N],id; //时间戳，最早出现的祖先， 编号
int cg[N],col; //color
int w[N],val[N]; //点权，缩点之后的点权
bool vs[N]; //是否在栈中
il void dfs(int u){
stk[++tp]=u;
vs[u]=1;
dfn[u]=low[u]=++id;
for(ri int i=he[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v);
low[u]=min(low[u],low[e[i].v]);
}
else if(vs[e[i].v]){
low[u]=min(low[u],dfn[e[i].v]);
}
}
if(dfn[u]==low[u]){
col++;
while(stk[tp+1]!=u){
cg[stk[tp]]=col;
val[col]+=w[stk[tp]];
vs[stk[tp--]]=0;
}
}
return;
}
} using namespace tarjan;
namespace topo_sort{
int in[N],f[N];
il void getdag(int m){
for(ri int i=1;i<=m;++i){
if(cg[e[i].u]!=cg[e[i].v]){
addo(cg[e[i].u],cg[e[i].v]);
in[cg[e[i].v]]++;
}
}
}
il int topo(int col,int m){
getdag(m);
queue<int> q;
int as=0;
for(ri int i=1;i<=col;++i){
if(!in[i]){
q.push(i),f[i]=val[i];
}
}
while(!q.empty()){
int u=q.front();q.pop();
for(ri int i=ho[u];i;i=o[i].nxt){
f[o[i].v]=max(f[o[i].v],f[u]+val[o[i].v]);
in[o[i].v]--;
if(!in[o[i].v]) q.push(o[i].v);
}
}
for(ri int i=1;i<=col;++i){
as=max(as,f[i]);
}
return as;
}
} using namespace topo_sort;
signed main(){
int n,m;
cin>>n>>m;
for(ri int i=1;i<=n;++i) cin>>w[i];
for(ri int i=1,u,v;i<=m;++i){
cin>>u>>v;adde(u,v,i);
}
for(ri int i=1;i<=n;++i){
if(!dfn[i]) dfs(i);
}
cout<<topo(col,m);
return 0;
}
割点
to be continue~
namespace tarjan{
int id,dfn[N],low[N],cnt;
bool vs[N],cut[N];
il void dfs(cs int u,cs int rt){
int son=0;
dfn[u]=low[u]=++id;
for(ri int i=h[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v,rt);
low[u]=min(low[u],low[e[i].v]);
if(low[e[i].v]>=dfn[u]&&u^rt&&!cut[u]) cut[u]=1,cnt++;
if(!(u^rt)) son++;
}
low[u]=min(low[u],dfn[e[i].v]);
}
if(!(u^rt)&&son>1&&!cut[rt]) cut[rt]=1,cnt++;
}
} using namespace tarjan;
code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
}using namespace Q;
cs int N=2e4+1,M=1e5+1;
int n,m,h[N];
namespace edge{
struct qwq{
int v,nxt;
}e[M<<1];
il void add(cs int u,cs int v,cs int i){
e[i*2-1]={v,h[u]},h[u]=i*2-1;
e[i<<1]={u,h[v]},h[v]=i<<1;
}
} using namespace edge;
namespace tarjan{
int id,dfn[N],low[N],cnt;
bool vs[N],cut[N];
il void dfs(cs int u,cs int rt){
int son=0;
dfn[u]=low[u]=++id;
for(ri int i=h[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v,rt);
low[u]=min(low[u],low[e[i].v]);
if(low[e[i].v]>=dfn[u]&&u^rt&&!cut[u]) cut[u]=1,cnt++;
if(!(u^rt)) son++;
}
low[u]=min(low[u],dfn[e[i].v]);
}
if(!(u^rt)&&son>1&&!cut[rt]) cut[rt]=1,cnt++;
}
} using namespace tarjan;
signed main(){
n=rd(),m=rd();
for(ri int i=1;i<=m;++i){
add(rd(),rd(),i);
}
for(ri int i=1;i<=n;++i){
if(!dfn[i]) dfs(i,i);
}
wt(cnt),putchar('\n');
for(ri int i=1;i<=n;++i){
if(cut[i]) wt(i),putchar(' ');
}
return 0;
}
边双连通分量
to be continue~
namespace tarjan{
int id,dfn[N],low[N],cnt;
bool bridge[M],vs[N];
vector<int> dcc[N];
il void dfs(cs int u,cs int edg){
dfn[u]=low[u]=++id;
for(ri int i=h[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v,i);
if(low[e[i].v]>dfn[u]) bridge[i>>1]=1;
low[u]=min(low[u],low[e[i].v]);
}
else if(i!=(edg^1)){
low[u]=min(low[u],dfn[e[i].v]);
}
}
return;
}
il void cntdcc(int u){
vs[u]=1,dcc[cnt].push_back(u);
for(ri int i=h[u];i;i=e[i].nxt){
if((!vs[e[i].v])&&(!bridge[i>>1])){
cntdcc(e[i].v);
}
}
return;
}
} using namespace tarjan;
code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
} using namespace Q;
cs int N=5e5+1,M=2e6+1;
int n,m,h[N];
namespace edge{
struct qwq{
int v,nxt;
}e[M<<1];
il void add(cs int u,cs int v,cs int i){
if(u==v) return;
e[(i<<1)|1]={u,h[v]},h[v]=(i<<1)|1;
return e[i<<1]={v,h[u]},h[u]=i<<1,void();
}
} using namespace edge;
namespace tarjan{
int id,dfn[N],low[N],cnt;
bool bridge[M],vs[N];
vector<int> dcc[N];
il void dfs(cs int u,cs int edg){
dfn[u]=low[u]=++id;
for(ri int i=h[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v,i);
if(low[e[i].v]>dfn[u]) bridge[i>>1]=1;
low[u]=min(low[u],low[e[i].v]);
}
else if(i!=(edg^1)){
low[u]=min(low[u],dfn[e[i].v]);
}
}
return;
}
il void cntdcc(int u){
vs[u]=1,dcc[cnt].push_back(u);
for(ri int i=h[u];i;i=e[i].nxt){
if((!vs[e[i].v])&&(!bridge[i>>1])){
cntdcc(e[i].v);
}
}
return;
}
} using namespace tarjan;
signed main(){
n=rd(),m=rd();
for(ri int i=1;i<=m;++i){
add(rd(),rd(),i);
}
for(ri int i=1;i<=n;++i){
if(!dfn[i]) dfs(i,0);
}
for(ri int i=1;i<=n;++i){
if(!vs[i]){
cnt++;
cntdcc(i);
}
}
wt(cnt),putchar('\n');
for(ri int i=1;i<=cnt;++i){
wt(dcc[i].size()),putchar(' ');
for(int u:dcc[i]) wt(u),putchar(' ');
putchar('\n');
}
return 0;
}
点双连通分量
to be continue~
namespace tarjan{
int id,stk[N],tl,dfn[N],low[N],cnt;
bool vs[N],cut[N];
vector<int> dcc[N];
il void dfs(cs int u,cs int rt){
dfn[u]=low[u]=++id,stk[++tl]=u;
for(ri int i=h[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v,rt);
low[u]=min(low[u],low[e[i].v]);
if(low[e[i].v]>=dfn[u]){
dcc[++cnt].push_back(u);
while(stk[tl+1]!=e[i].v){
dcc[cnt].push_back(stk[tl--]);
}
}
}
low[u]=min(low[u],dfn[e[i].v]);
}
}
} using namespace tarjan;
code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
} using namespace Q;
cs int N=5e5+1,M=2e6+1;
int n,m,h[N];
namespace edge{
struct qwq{
int v,nxt;
}e[M<<1];
il void add(cs int u,cs int v,cs int i){
if(u==v) return;
e[i*2-1]={v,h[u]},h[u]=i*2-1;
e[i<<1]={u,h[v]},h[v]=i<<1;
}
} using namespace edge;
namespace tarjan{
int id,stk[N],tl,dfn[N],low[N],cnt;
bool vs[N],cut[N];
vector<int> dcc[N];
il void dfs(cs int u,cs int rt){
dfn[u]=low[u]=++id,stk[++tl]=u;
for(ri int i=h[u];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs(e[i].v,rt);
low[u]=min(low[u],low[e[i].v]);
if(low[e[i].v]>=dfn[u]){
dcc[++cnt].push_back(u);
while(stk[tl+1]!=e[i].v){
dcc[cnt].push_back(stk[tl--]);
}
}
}
low[u]=min(low[u],dfn[e[i].v]);
}
}
} using namespace tarjan;
//如果你90ptsWA on #1 #11
//可能是因为没判自环
signed main(){
n=rd(),m=rd();
for(ri int i=1;i<=m;++i){
add(rd(),rd(),i);
}
for(ri int i=1;i<=n;++i){
if(!dfn[i]){
if(!h[i]) dcc[++cnt].push_back(i);
else dfs(i,i);
}
}
wt(cnt),putchar('\n');
for(ri int i=1;i<=cnt;++i){
wt(dcc[i].size()),putchar(' ');
for(int u:dcc[i]) wt(u),putchar(' ');
putchar('\n');
}
return 0;
}