P3387 【模板】缩点(强连通分量+拓扑+dp)
#include<iostream>
#include<queue>
#include<cmath>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define mp(a,b) make_pair(a,b)
using namespace std;
struct node{
int from;
int to;
int nex;
}a[500005],b[500005];
queue <int > dl;
int hd[500005],hd2[500005],cnt,cnt2,w[500005];
//a为原图，b为缩点后的图
int n,m,u,v,in[500005],dfn[500005],low[5000005],jl[500005],t,zhan[500005],top,ans[5000005];
//in记录b图的入度，dfn时间戳，low遇到的最小的时间戳，jl记录节点i属于哪一个强连通分量,t为时间,zhan为记录在同一个强连通分量中的节点
bool vis[500005];
void ru(int x,int y)
{
a[++cnt].from=x;
a[cnt].to=y;
a[cnt].nex=hd[x];
hd[x]=cnt;
}
void ru2(int x,int y)
{
b[++cnt2].from=x;
b[cnt2].to=y;
b[cnt2].nex=hd2[x];
hd2[x]=cnt2;
in[y]++;
}
void tarjan(int x)
{
dfn[x]=++t;
low[x]=t;
zhan[++top]=x;
vis[x]=1;
for(int i=hd[x];i;i=a[i].nex)
{
int y=a[i].to;
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
if(vis[y]) low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x])//找到了这个强连通分量的所有点了
{
int y=1;
while(y)
{
y=zhan[top--];
jl[y]=x;
vis[y]=0;
if(x==y) break;
w[x]+=w[y];
}
}
return ;
}
int tuopu()
{
for1(i,1,n) if(in[i]==0&&jl[i]==i) dl.push(i),ans[i]=w[i];
while(!dl.empty())
{
int ji=dl.front();
dl.pop();
for(int i=hd2[ji];i;i=b[i].nex)
{
int y=b[i].to;
ans[y]=max(ans[y],ans[ji]+w[y]);
in[y]--;
if(in[y]==0) dl.push(y);
}
}
int mx=-1;
for1(i,1,n)
mx=max(mx,ans[i]);
return mx;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for1(i,1,n)scanf("%d",&w[i]);
for1(i,1,m)
scanf("%d%d",&x,&y)
,ru(x,y);
for1(i,1,n)
if(dfn[i]==0)
tarjan(i);
for1(i,1,m)
{
u=jl[a[i].from],v=jl[a[i].to];
if(u!=v)//如果不在同一强连通分量
ru2(u,v);
}
cout<<tuopu();
return 0;
}
P3388 【模板】割点（割顶）
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define mp(a,b) make_pair(a,b)
using namespace std;
struct node{
int from;
int to;
int nex;
}a[500005];
int hd[500005],cnt;
int n,m,cut[500005],dfn[500005],low[5000005],t,ans;
//dfn时间戳，low遇到的最小的时间戳,t为时间,cut[i]记录节点 i 是否为割点
void ru(int x,int y)
{
a[++cnt].from=x;
a[cnt].to=y;
a[cnt].nex=hd[x];
hd[x]=cnt;
}
void tarjan(int x,int fa)//fa为祖先
{
dfn[x]=low[x]=++t;
int kid=0;//以 fa 这个根节点的子树个数
for(int i = hd[x];i;i=a[i].nex)
{
int v=a[i].to;
if(!dfn[v])
{
tarjan(v,fa);
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]&&x!=fa) //x并不是根节点同时 x 的祖先与 v只能通过 x 相连，所以x 可以是割点
cut[x]=1;
if(x==fa) kid++;//如果枚举的节点是根节点，子树个数++，因为这个节点还没有被访问过，所以如果想到达他就需要经过 fa 节点
}
low[x]=min(low[x],dfn[v]);//易错点，直接硬背（好像无向图都是要这样？）
}
if(kid>1&&x==fa) cut[x]=1;//如果根节点有两个以上的子树，那么他就应当是割点
}//判定一个点是否是根节点有两种情况，一种是发现low[son]>=dfn[fa]同时不是枚举的根节点
//另一种是根节点有了两个以上的子树
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for1(i,1,m)
{
scanf("%d%d",&x,&y);
ru(x,y);
ru(y,x);
}
for1(i,1,n)
if(!dfn[i]) tarjan(i,i);
for1(i,1,n)
ans+=cut[i];
printf("%d\n",ans);
for1(i,1,n)
if(cut[i]) printf("%d ",i);
return 0;
}
2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
const int maxn=500005;
using namespace std;
struct node{
int from;
int nex;
int to;
}a[500005];
int hd2[maxn];
int zhan[maxn],top;
int hd[maxn],cnt,w[maxn],n,m,dfn[maxn],low[maxn],vis[maxn],ji,sd[maxn],ans;
int size[500005],jl,out[500005];
void ru(int x,int y)
{
a[++cnt].to=y;
a[cnt].from=x;
a[cnt].nex=hd[x];
hd[x]=cnt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++ji;
zhan[++top]=x;vis[x]=1;
for(int i=hd[x];i;i=a[i].nex)
{
int v=a[i].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[v],low[x]);
}
else if(vis[v]) low[x]=min(low[v],low[x]);
}
if(dfn[x]==low[x])
{
vis[x]=0;
sd[x]=++jl;
size[jl]=1;
while (x!=zhan[top])
{
size[jl]++;
sd[zhan[top]]=jl;
vis[zhan[top]]=0;
top--;
}
top--;
}
return ;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for1(i,1,m)
{
scanf("%d%d",&x,&y);
ru(x,y);
}
for1(i,1,n)
if(dfn[i]==0)
tarjan(i);
for1(i,1,m)
{
int u=sd[a[i].from],v=sd[a[i].to];
if(u!=v)
out[u]++;
}
int kg=0;
for1(i,1,jl)
{
if(out[i]==0)
{
ans+=size[i];
kg++;
}
}
if(kg==1)
cout<<ans;
else
cout<<0;
return 0;
}
桥10102. 「一本通 3.6 练习 3」旅游航道：
与割点做法差不多只是判定条件变成了如果low[v] > dnf[u] ，表示（u，v）这条边为桥
#include <bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int n, m;
struct node {
int nex;
int to;
} a[500005];
int hd[100006];
int cnt = 0;
int ans;
void ru(int x, int y) {
cnt++;
a[cnt].to = y;
a[cnt].nex = hd[x];
hd[x] = cnt;
return ;
}
int dfn[100006], low[100006];
int tot = 0;
void tarjan(int x, int fa) {
dfn[x] = low[x] = ++tot;
for (int i = hd[x]; i; i = a[i].nex) {
int v = a[i].to;
if (!dfn[v]) {
tarjan(v, x);
low[x] = min(low[x], low[v]);
if (low[v] > dfn[x])
ans++;
} else if (v != fa)
low[x] = min(low[x], dfn[v]);
}
return ;
}
int main() {
while (1) {
cin >> n >> m;
if (n == 0 && m == 0)
return 0;
int x, y;
for1(i, 1, m) {
cin >> x >> y;
ru(x, y);
ru(y, x);
}
for1(i, 1, n) if (!dfn[i])
tarjan(i, i);
cout << ans << endl;
ans = 0;
for1(i, 1, cnt) a[i] = (node) {
0, 0
};
for1(i, 1, n) hd[i] = 0;
for1(i, 1, n) dfn[i] = 0, low[i] = 0;
cnt = 0;
}
return 0;
}
点双联通分量：
表示一个无向图中没有割点的极大联通子图。
在割点代码的基础上，增加一个栈，每次访问一个点时将点压入栈中，如果发现该点是割点，就弹出栈中的点，直到弹出的是那个割点，这些点在同一个点双连通分量中
边双联通分量：
表示一个无向图中没有桥的极大联通子图。（极大？）
先求出所有割边，然后全都删掉，剩下的联通图就都是边双连通分量了。
标签：Tarjan,int,dfn,low,ans,for1,节点 From： https://www.cnblogs.com/yyx525jia/p/16729104.html