最近遇到了这种模板题，记录一下
tarjan求桥，求割
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
#define MX 1005 int n, m, Ddex;
vector<int> G[MX];
int fat[MX];
int low[MX],dfn[MX];
bool is_cut[MX]; void Init()
{
Ddex=;
for (int i=;i<=n;i++) G[i].clear();
memset(dfn,-,sizeof(dfn));
memset(fat,-,sizeof(fat));
memset(is_cut,,sizeof(is_cut));
} void Tarjan(int i,int pre)
{
fat[i]=pre;
dfn[i]=low[i]=++Ddex;
for(int j=;j<G[i].size();++j)
{
int k=G[i][j];
if(dfn[k]==-)
{
Tarjan(k,i);
low[i]=min(low[i],low[k]);
}
else if(k!=pre) //假如k是i的父亲的话，那么这就是无向边中的重边，有重边那么一定不是桥*/
low[i]=min(low[i],dfn[k]);
}
}
void calc()
{
int rootson=;
Tarjan(,-);
for(int i=;i<=n;++i)
{
int v=fat[i];
if(v==)
rootson++; //统计根节点子树的个数，根节点的子树个数>=2,就是割点
else{
if(low[i]>=dfn[v]) //割点的条件
is_cut[v]=true;
}
}
if(rootson>)
is_cut[]=true;
for(int i=;i<=n;++i)
if(is_cut[i])
printf("%d\n",i); for(int i=;i<=n;++i)
{
int v=fat[i];
if(v>&&low[i]>dfn[v])//桥的条件
printf("%d, %d\n",i,v);
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
Init();
int a,b;
for(int i=;i<=m;++i)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
calc();
}
return ;
}
求强连通缩点加拓扑排序。。。