tarjan求无向图割点，若x是根节点，则子树个数>1时x时割点；若x是非根节点，当ipt[x]<=low[y]时x是割点，说明y的子树无法通过非父子边回溯到x的祖先，那么删掉x，图将分裂成两个字图，即x是割点。
void tarjan(int x,int root){
ipt[x]=low[x]=++dfn;
int son=0;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
son++;/*统计子树个数*/
tarjan(y,root);
low[x]=min(low[x],low[y]);
if(ipt[x]<=low[y]&&(x!=root||son>1))cut[x]=true;/*非根节点或子树数量>1则是割点*/
}
else low[x]=min(low[x],ipt[y]);
}
}
tarjan求无向图割边，对于点x，若ipt[x]<low[y]，说明y无法通过非父子边回到x，更无法回到x的祖先，那么删掉边(x,y)图就会分裂成两个子图，即这条边是割边。
void tarjan(int x,int eid){
ipt[x]=low[x]=++dfn;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(ipt[x]<low[y])bridge.insert({x,y});//链式前向星初始化tot=1
}
else if(i!=(eid^1))low[x]=min(low[x],ipt[y]);
}
}
tarjan无向图求点双联通分量，一个割点可以属于多个不同的点双联通分量，维护一个进入搜索树中的栈，若遇到割点x，把点接连从栈顶取出直到y且不取出y，这些点和x组成一个点双联通分量。
void tarjan(int x,int fa){
ipt[x]=low[x]=++dfn;
s[++s[0]]=x;
int son=0;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
son++;
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(ipt[x]<=low[y]){
vdcc[++cnt].push_back(x);//加入割点或树根
int z;
do{
z=s[s[0]--];
vdcc[cnt].push_back(z);
}while(z!=y);
}
}
else if(y!=fa)low[x]=min(low[x],ipt[y]);
}
if(!fa&&!son)vdcc[++cnt].push_back(x);//对于孤立节点的特判
}
tarjan无向图求边双联通分量，在求割边后，一个强连通分量中的点可以互相到达，两个强连通分量中的点不可以互相到达，边双联通分量是没有桥的联通分量，若tarjan一遍更新后x的low没有变化，那么x已经是边界，只要有一个分量中没有割边，那么在tarjan求割边的搜索树中一定强连通，该分量在原图中一定是一个边双联通分量。
void tarjan(int x,int eid){
ipt[x]=low[x]=++dfn;
s[++s[0]]=x;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
}
else if(i!=(eid^1))low[x]=min(low[x],ipt[y]);//注意要位运算优先级较低，要加括号，并且链式前向星tot初始化=1
}
if(ipt[x]==low[x]){//x是边界，x到栈顶的点构成了边双联通分量
int y;
cnt++;
do{
y=s[s[0]--];
edcc[cnt].push_back(y);
}while(x!=y);
}
}
tarjan有向图求强连通分量，维护一个栈，对于点x，若在一遍更新后ipt[x]=low[x]，那么说明x的子树中刚好有边可以指回x且无法指向x的祖先，此时x和栈中的点构成了一个强连通分量。
void tarjan(int x){
ipt[x]=low[x]=++dfn;
s[++s[0]]=x;
in[x]=1;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(in[y])low[x]=min(low[x],ipt[y]);//对于在栈中的点才对更新low值有用
}
if(ipt[x]==low[x]){
int y;
cnt++;
do{
y=s[s[0]--];
in[y]=0;//在栈中的标记要清空
bl[y]=cnt;
scc[cnt].push_back(y);
sum[cnt]+=a[y];//将权值缩到一起
}while(x!=y);
}
}
当然也可以省去in数组，用bl来判断是否在栈中。
void tarjan(int x){
ipt[x]=low[x]=++dfn;
s[++s[0]]=x;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(!bl[y])low[x]=min(low[x],ipt[y]);
}
if(ipt[x]==low[x]){
int y;
cnt++;
do{
y=s[s[0]--];
bl[y]=cnt;
scc[cnt].push_back(y);
sum[cnt]+=a[y];
}while(x!=y);
}
}
tarjan无向图点双联通分量缩点，若原图有a个割点和b和点双联通分量，那么缩点后总共有a+b个点，对于每个割点，给一个新的编号，可以从vdcc的个数+1开始编号，便利每一个vdcc内的点，将该vdcc的编号和内部的割点进行连边。
int num=cnt;
for(int i=1;i<=n;i++)if(cut[i])newid[i]=++num;
for(int i=1;i<=cnt;i++){
for(auto x:vdcc[i]){
if(cut[x]){
v[i].push_back(newid[x]);
v[newid[x]].push_back(i);
}
}
}
tarjan无向图边双联通分量缩点，枚举边，不在同一个边双中的点，将两个边双连边。
for(int i=1;i<=m;i++){
int x=bl[e[i].from],y=bl[e[i].to];
if(x!=y)v[x].push_back(y),v[y].push_back(x);
}
tarjan有向图强连通分量缩点，枚举每条边，对于不在同一个缩点中的点，将两个缩点集合连边。
for(int i=1;i<=m;i++){
int x=bl[e[i].from],y=bl[e[i].to];
if(x!=y)v[x].push_back(y),rd[y]++;
}
给定起止点，问中间路径上的毕竟点。从起点开始tarjan，考虑缩点，对于非起始点的割点x，需要判断终止点是否在y的子树内，若ipt[y]<=ipt[ed]，则说明ed存在于y的子树内。
void tarjan(int x){
ipt[x]=low[x]=++dfn;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(ipt[x]<=low[y]&&x!=st&&ipt[y]<=ipt[ed])ans=min(ans,x);
}
else low[x]=min(low[x],ipt[y]);
}
}
有依赖关系的软件，每个软件体积为w，价值为v，若无法正常工作则它的价值为0，求最大的价值。按照依赖关系连边，求出SCC后缩点，建新图跑树形背包dp，f[i][j]表示以i为根的子树中体积不超过j的最大价值，注意缩点后0要向入读为0的强连通分量连一条边，之后转化成一棵以0位根的树。
void dfs(int x){
for(int i=sw[x];i<=m;i++)f[x][i]=sa[x];/*sw是体积总和，sa是价值总和*/
for(auto y:v[x]){
dfs(y);
for(int i=m-sw[x];i>=0;i--)
for(int j=0;j<=i;j++)
f[x][i+sw[x]]=max(f[x][i+sw[x]],f[y][j]+f[x][i+sw[x]-j]);
}
}
在一个DAG中，求最少加多少条边使得其变成一个SCC。统计出入度为0的点，去两者个数中的较大者。
for(int i=1;i<=cnt;i++)re+=rd[i]==0,ans+=cd[i]==0;
if(cnt==1)cout<<0;
else cout<<max(re,ans);
n个游戏，趣味程度w，玩完后兴奋程度为e，每次只会玩趣味程度是兴奋程度整倍数的游戏，初始兴奋度为1，问是否有游戏可以玩两次。将每个数向自己的倍数连边，时间复杂度N*log2(N)，每个游戏的w向自己的e连边，缩点后判断是否有一个游戏的w和e在同一个强连通分量中即可。边数不好计算，使用vector存图。
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n;i++)cin>>p[i],add(w[i],p[i]);
for(int i=1;i+i<N;i++)for(int j=2;i*j<N;j++)add(i,i*j);
tarjan(1);
int re=0;
for(int i=1;i<=n;i++)re+=bl[w[i]]==bl[p[i]];
cout<<re<<'\n';
可以从任意一个顶点出发前往任意一个岛屿并立即返回，输入n个点对表示在同一岛屿上的相邻顶点，之后一个矩阵表示顶点间的费用，求到达所有岛屿的最小费用。将顶点对进行缩点，缩点间的连边转化为岛屿间的航线，枚举一个岛屿为起始点并计算答案即可。
memset(w,0x3f,sizeof(w));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
int x;cin>>x;w[bl[i]][bl[j]]=min(w[bl[i]][bl[j]],x);
}
for(int i=1;i<=cnt;i++){
int re=0;
for(int j=1;j<=cnt;j++)if(i!=j)re+=w[i][j];
ans=min(ans,re);
}
cout<<ans*2;
给定无向图，k个点属于集合a，l个点属于集合b，求有多少条边满足删去后原图存在若干个点与至少一个集合中的所有点都不联通。答案肯定在割边当中，当集合a或b全部在或全部不在y的子树中且x是割边时，那么这条边时合法的答案。
void tarjan(int x,int eid){
ipt[x]=low[x]=++dfn;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!ipt[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(ipt[x]<low[y]&&(!a[y]||!b[y]||a[y]==k||b[y]==l))ans.insert({x,y});
a[x]+=a[y];
b[x]+=b[y];
}
else if(i!=(eid^1))low[x]=min(low[x],ipt[y]);
}
}
有向图从1出发回到1，至多允许逆行一次，求做多可以经过多少个不同的点。首先进行缩点，环中的点都可以任意到达，缩点后建正反图，分别跑spfa最长路，dis就是路径上经过的点的数量，最后枚举每一个SCC和它连接着的另一个SCC，判断在这条边逆行后的最大价值，ans初始化1所在SCC的大小，因为可能无法走出去。
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
g.add(a,b);
}
for(int i=1;i<=n;i++)if(!ipt[i])g.tarjan(i);
for(int x=1;x<=n;x++)for(auto y:g.v[x])if(bl[x]!=bl[y])g0.add(bl[x],bl[y]),g1.add(bl[y],bl[x]);
g0.spfa(bl[1]);
g1.spfa(bl[1]);
int ans=scc[bl[1]].size();
for(int x=1;x<=cnt;x++)if(g0.dis[x])for(auto y:g1.v[x])if(g1.dis[y])ans=max(ans,g0.dis[x]+g1.dis[y]-(int)scc[bl[1]].size());
cout<<ans;
return 0;
}
给定有向图，两点之间的多条道路被认为是不同的道路，问从哪些点前往n+1号点的路线数量最多，若超过36500则按照36500算。终点固定，建返图，跑tarjan，统计一个SCC内的点的数量，若大于1则方案书无无限，注意这里自环也应该算进去，之后拓扑排序求方案数，对36501取min，之后输出方案，注意方案是针对单个点，而不是SCC的，所以枚举单个点，用其所在SCC的dp值进行判断。
inline void topo(){
queue<int>q;
for(int i=1;i<=cnt;i++)if(!rd[i])q.push(i);
f[bl[n+1]]=1;
vis[bl[n+1]]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(auto y:v[x]){
if(!--rd[y])q.push(y);
vis[y]|=vis[x];
f[y]=min(36501,f[x]+f[y]);
if(sz[y]>1)f[y]=36501;
}
}
}
for(int i=1;i<=n+1;i++)if(!ipt[i])tarjan(i);
for(int i=1;i<=m;i++){
int x=bl[e[i].from],y=bl[e[i].to];
if(x!=y)v[x].push_back(y),rd[y]++;
else sz[x]++;
}
topo();
for(int i=1;i<=cnt;i++)if(vis[i])ans=max(ans,f[i]);
tot=0;
for(int i=1;i<=n;i++)if(vis[bl[i]]&&f[bl[i]]==ans)tot++;
if(ans==36501)cout<<"zawsze\n";
else cout<<ans<<'\n';
cout<<tot<<'\n';
for(int i=1;i<=n;i++)if(vis[bl[i]]&&f[bl[i]]==ans)cout<<i<<' ';
跑步比赛给出一些关系，第一种a的成绩正好比b快一秒，第二种c的成绩比d快，问所有参赛者最多能达到多少种不同的成绩。差分约束连边，两个点若可以互相到达，则它们的差值关系是确定的，进行缩点，对于一个SCC，所有点之间的最短路的最大值加一就是这个SCC的答案。若两个点之间是单向的或没有关系，那么就无法确定差值关系。
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++)dis[i][i]=0;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b,-1);
add(b,a,1);
dis[a][b]=min(dis[a][b],-1);
dis[b][a]=min(dis[b][a],1);
}
for(int i=1;i<=k;i++){
int a,b;
cin>>a>>b;
add(a,b,0);
dis[a][b]=min(dis[a][b],0);
}
for(int i=1;i<=n;i++)if(!ipt[i])tarjan(i);
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(bl[i]!=bl[k]||dis[i][k]==0x3f3f3f3f)continue;
for(int j=1;j<=n;j++){
if(bl[i]!=bl[j])continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
for(int i=1;i<=n;i++)if(dis[i][i]<0)return cout<<"NIE",0;
int ans=0;
for(int i=1;i<=cnt;i++){
int ma=0;
for(auto x:scc[i])for(auto y:scc[i])ma=max(ma,dis[x][y]);
ans+=ma+1;
}
cout<<ans;