Tarjan
概述
tarjan问题主要处理有向图的强连通分量和无向图的割点桥甚至是LCA问题，本文主要介绍前两者，后者请看之前的博客。
强连通分量
这类的问题主要是判环问题，是否在子图中存在两两互通的点。
思路是随意选择一个点作为根节点，然后做一个分层图的思路，根据到达的时间做一个dfn记录，接下来用low去判断它能回到的最早点，因为有环存在的原因，当前点要么可以更新，要不不可以更新，前者的情况因为它是在子图里面的最早的点，所以无法更新，我们用栈记录它的时候，它就是最后出栈的点；如果可以更新的话要不通过下一个点来进行更新，要不就通过最早的点更新，我们直接做一个dfs回溯即可。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int n,m,idx,sta[maxn],tot=0,cnt;
int dfn[maxn],low[maxn],head[maxn],vis[maxn];
struct Edge{
int next,to;
}edge[maxn<<1];
void add(int a,int b) {
edge[idx]=(Edge){head[a],b},head[a]=idx++;
}
void dfs(int p)
{
sta[++tot]=p; vis[p]=1;
dfn[p]=low[p]=++cnt;
for(int i=head[p];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(!dfn[ver]) dfs(ver),low[p]=min(low[p],low[ver]);
else if(vis[p]) low[p]=min(low[p],dfn[ver]);
}
if(low[p]==dfn[p])
{
int t=low[p];
while(low[sta[tot]]==t&&tot!=0)
vis[sta[tot]]=0,printf("%d ",sta[tot--]);
printf("\n");
}
}
int main()
{
memset(head,-1,sizeof head);
memset(dfn,0,sizeof dfn);
memset(vis,0,sizeof vis);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) dfs(i);
return 0;
}缩点
在一个有向图中，每一个点都有权值，求一条路线可以得到最大的权值和，路可以重复。
思路是直接把一个连通分量里的点缩成一个点集合，然后重新建图即可，最后做一遍拓补排序，这里拓补是直接进行max取值，而不是计数所以不用考虑重复读边的情况。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,cnt=0,top=0;
int head1[N],head2[N],idx1=0,idx2=0,vis[N],dist[N];
int sta[N],q[N],low[N],dfn[N],fa[N],p[N],in[N];
struct Edge{
int next,from,to;
}edge[M],edges[M];
void add(int a,int b) {
edge[idx1]=(Edge){head1[a],a,b},head1[a]=idx1++;
}
void tarjan(int u)
{
low[u]=dfn[u]=++cnt;
sta[++top]=u,vis[u]=true;
for(int i=head1[u];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(!dfn[ver]){
tarjan(ver);
low[u]=min(low[u],low[ver]);
}
else if(vis[ver]) low[u]=min(low[u],dfn[ver]);
}
if(dfn[u]==low[u])
{
int tmp;
while(tmp=sta[top--])
{
fa[tmp]=u;
vis[tmp]=false;
if(tmp==u) break;
p[u]+=p[tmp];
}
}
}
int Sort()
{
int hh=0,tt=0;
for(int i=1;i<=n;i++)
if(fa[i]==i&&!in[i])
{
q[++tt]=i;
dist[i]=p[i];
}
while(hh<=tt)
{
int t=q[hh++];
for(int i=head2[t];~i;i=edges[i].next)
{
int ver=edges[i].to;
dist[ver]=max(dist[ver],dist[t]+p[ver]);
if(--in[ver]==0) q[++tt]=ver;
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dist[i]);
return ans;
}
int main()
{
memset(head1,-1,sizeof head1);
memset(head2,-1,sizeof head2);
memset(vis,false,sizeof vis);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i,scanf("%d",&p[i]);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=0;i<idx1;i++)
{
int x=fa[edge[i].from],y=fa[edge[i].to];
if(x!=y)
{
edges[idx2]=(Edge){head2[x],x,y};
head2[x]=idx2++;
in[y]++;
}
}
printf("%d\n",Sort());
return 0;
}割点
在一个无向图中，删除某个点和它的边使他不连通，则称为割点。
我们可以根据之前的思路来做，它回溯到当前点的子节点，本身，父节点三种情况，但是只有前两种的情况是满足的，毕竟是一个无向图。注意如果是一个根节点的话要做一下特判，是不是存在2个及以上的子图。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e4+10,M=2e5+10;
int n,m,cnt,ans=0;
int head[N],idx;
int dfn[N],low[N];
bool cut[N];
struct Edge{
int next,to;
}edge[M];
void add(int a,int b)
{
edge[idx]=(Edge){head[a],b},head[a]=idx++;
edge[idx]=(Edge){head[b],a},head[b]=idx++;
}
void tarjan(int u,int root)
{
int rc=0;
dfn[u]=low[u]=++cnt;
for(int i=head[u];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(!dfn[ver]){
tarjan(ver,root);
low[u]=min(low[u],low[ver]);
if(low[ver]>=dfn[u]&&u!=root) cut[u]=true;
if(u==root) rc++;
}
low[u]=min(low[u],dfn[ver]);
}
if(u==root&&rc>=2) cut[root]=true;
}
int main()
{
memset(cut,false,sizeof cut);
memset(head,-1,sizeof head);
memset(dfn,0,sizeof dfn);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,i);
for(int i=1;i<=n;i++) if(cut[i]) ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
return 0;
}