tarjan一直是我看了头大的问题，省选之前还是得好好系统的学习一下。我按照不同的算法在hdu上选题练习了一下，至少还是有了初步的认识。tarjan嘛，就是维护一个dfsnum[]和一个low[]，在dfs树上处理图的连通性等问题。细节处的不同导致算法本身的不同作用。
有向图强连通缩点：大体思路是维护一个栈，满足访问一个点就push到栈里面，当满足low[now]==dfn[now]时出栈，用dfn[]更新low[]当且仅当下一个点在栈内（注意不是递归栈）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 2200
#define MAXV MAXN
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
struct Edge
{
int np;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y)
{
E[++tope].np=y;
E[tope].next=V[x];
V[x]=&E[tope];
}
int status[MAXN];
int stack[MAXN],tops=-;
int low[MAXN],dfn[MAXN],dfstime;
int top[MAXN];
void tarjan(int now)
{
status[now]=;
stack[++tops]=now;
low[now]=dfn[now]=++dfstime;
Edge *ne;
for (ne=V[now];ne;ne=ne->next)
{
if (status[ne->np]==)
{
low[now]=min(low[now],dfn[ne->np]);
}else if (status[ne->np]==)
{
tarjan(ne->np);
low[now]=min(low[now],low[ne->np]);
}
}
if (low[now]==dfn[now])
{
while (stack[tops]!=now)
{
status[stack[tops]]=;
top[stack[tops--]]=now;
}
status[stack[tops]]=;
top[stack[tops--]]=now;
}
//status[now]=2;
}
int a[MAXN];
int el[MAXE][];
int degi[MAXN];
int cirv[MAXN]; int main()
{
freopen("input.txt","r",stdin);
int n,m,x,y,z;
while (~scanf("%d%d",&n,&m))
{
for (int i=;i<=n;i++)
scanf("%d",a+i);
for (int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
el[i][]=x;
el[i][]=y;
}
for (int i=;i<=n;i++)
if (!dfn[i])
tarjan(i);
for (int i=;i<=m;i++)
{
if (top[el[i][]]!=top[el[i][]])
degi[top[el[i][]]]++;
}
memset(cirv,INF,sizeof(cirv[])*(n+));
for (int i=;i<=n;i++)
cirv[top[i]]=min(cirv[top[i]],a[i]);
int ans2=,ans1=;
for (int i=;i<=n;i++)
{
if (top[i]==i && !degi[top[i]])
{
ans1++;
ans2+=cirv[top[i]];
}
}
printf("%d %d\n",ans1,ans2);
memset(V,,sizeof(V[])*(n+));
memset(dfn,,sizeof(dfn[])*(n+));
memset(degi,,sizeof(degi[])*(n+));
memset(status,,sizeof(status[])*(n+));
tope=-;
dfstime=;
}
}
hdu 1827
无向图求桥边：这种类型算是最简单的把，唯一要注意的是要记录每个“编号”的边是否访问，而不是点。
这道题我认认真真写的非递归tarjan，参考集训某些大神的非递归，让我领会到了非递归的“精髓”，以后再也不用类似于记录当前运行到什么语句的方法了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 210000
#define MAXV MAXN
#define MAXE 1100000*2
#define INF 0x3f3f3f3f
struct Edge
{
int np;
int id;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y,int id=)
{
E[++tope].np=y;
E[tope].next=V[x];
E[tope].id=id;
V[x]=&E[tope];
}
int status[MAXN];
int low[MAXN],dfn[MAXN],dfstime;
bool is_bridge[MAXE];
bool edge_vis[MAXE];
void tarjan(int now)
{
Edge *ne;
status[now]=;
low[now]=dfn[now]=++dfstime;
for (ne=V[now];ne;ne=ne->next)
{
if (edge_vis[ne->id])continue;
if (status[ne->np]==)
{
low[now]=min(low[now],dfn[ne->np]);
}else if (status[ne->np]==)
{
edge_vis[ne->id]=true;
tarjan(ne->np);
low[now]=min(low[now],low[ne->np]);
if (low[ne->np]==dfn[ne->np])
is_bridge[ne->id]=true;
}
}
}
int tarj_now[MAXN],tarj_step[MAXN];
Edge *tarj_ne[MAXN];
int lev=-;
#define ne tarj_ne[cur]
#define now tarj_now[cur]
void tarjan2(int root)
{
int cur=;
now=root;
ne=V[root];
status[now]=;
low[now]=dfn[now]=++dfstime;
while (true)
{
tarj_begin:
if (ne)
{
if (!edge_vis[ne->id])
{
if (status[ne->np]==)
low[now]=min(low[now],dfn[ne->np]);
else if (status[ne->np]==)
{
edge_vis[ne->id]=true;
tarj_now[cur+]=ne->np;
tarj_ne[cur+]=V[tarj_now[cur+]];
cur++;
status[now]=true;
low[now]=dfn[now]=++dfstime;
goto tarj_begin;
tarj_back:
low[now]=min(low[now],low[ne->np]);
if (low[ne->np]==dfn[ne->np])
is_bridge[ne->id]=true;
}
}
ne=ne->next;
}else
{
cur--;
if (cur==-)break;
goto tarj_back;
}
}
}
#undef now
#undef ne
int el[MAXE][];
int uf[MAXN];
int rk[MAXN];
int get_fa(int now)
{
return now==uf[now] ? now : uf[now]=get_fa(uf[now]) ;
}
void comb(int x,int y)
{
x=get_fa(x);
y=get_fa(y);
if (rk[x]>rk[y])
{
uf[y]=x;
rk[x]=max(rk[x],rk[y]+);
}else
{
uf[x]=y;
rk[y]=max(rk[y],rk[x]+);
}
}
int dis[MAXN];
int q[MAXN];
int pnt[MAXN];
int bfs(int now)
{
int head=-,tail=;
Edge *ne;
q[]=now;
dis[now]=;
pnt[now]=now;
int res=now;
while (head<tail)
{
now=q[++head];
if (dis[res]<dis[now])res=now;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
q[++tail]=ne->np;
dis[ne->np]=dis[now]+;
pnt[ne->np]=now;
}
}
return res;
} int main()
{
freopen("input.txt","r",stdin);
int n,m,x,y,z;
while (scanf("%d%d",&n,&m),n+m)
{
memset(V,,sizeof(V));
tope=-;
dfstime=;
memset(status,,sizeof(status));
memset(is_bridge,,sizeof(is_bridge));
memset(edge_vis,,sizeof(edge_vis));
memset(dfn,,sizeof(dfn));
int tot=;
for (int i=;i<=n;i++)
uf[i]=i,rk[i]=;
for (int i=;i<m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y,i);
addedge(y,x,i);
el[i][]=x;
el[i][]=y;
}
for (int i=;i<=n;i++)
if (!dfn[i])
tarjan2(i);
for (int i=;i<m;i++)
{
if (is_bridge[i])
tot++;
else
comb(el[i][],el[i][]);
}
for (int i=;i<=n;i++)
uf[i]=get_fa(i);
memset(V,,sizeof(V));
tope=-;
for (int i=;i<m;i++)
{
if (get_fa(el[i][])==get_fa(el[i][]))continue;
addedge(get_fa(el[i][]),get_fa(el[i][]));
addedge(get_fa(el[i][]),get_fa(el[i][]));
}
x=;
x=bfs(get_fa(x));
x=bfs(x);
printf("%d\n",tot-dis[x]);
}
}
hdu 4612
无向图求割点：这种类型很容易想错，而且也很难调试，首先我们需要对dfs的根节点分类讨论，其次，如果一个点有不止一次满足向下调用low[to]>=dfn[now]或不存在low[to]<=low[pnt]，则这个点是割点。
顺便吐槽一下，网上粘的标程没有一个靠谱的，真不知道数据要水成啥样才能把它们放过。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 5500
#define MAXE MAXN*2
#define INF 0x3f3f3f3f
#define MAXV MAXN
struct Edge
{
int np,id;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y,int id)
{
E[++tope].np=y;
E[tope].id=id;
E[tope].next=V[x];
V[x]=&E[tope];
}
bool edge_vis[MAXE];
int low[MAXN],dfn[MAXN];
int dfstime=;
int root;
int ans;
bool cut_p[MAXN];
int status[MAXN];
void tarjan(int now,int p)
{
int totd=;
dfn[now]=low[now]=++dfstime;
Edge *ne;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==p)continue;
if (!dfn[ne->np])
{ tarjan(ne->np,now);
if (low[ne->np]>=dfn[now])
totd++;
low[now]=min(low[now],low[ne->np]);
}else
{
low[now]=min(low[now],dfn[ne->np]);
}
}
ans=max(ans,(totd+(now!=root))-);
}
int el[MAXE][]; int main()
{
freopen("input.txt","r",stdin);
int x,y,z,n,m;
while (~scanf("%d %d\n",&n,&m))
{
for (int i=;i<m;i++)
{
scanf("%d%d",&x,&y);
x++;y++;
el[i][]=x;
el[i][]=y;
}
int res=;
int tot;
for (int i=;i<=n;i++)
{
ans=-INF;
tot=;
memset(V,,sizeof(V));
tope=-;
dfstime=;
memset(dfn,,sizeof(dfn));
for (int j=;j<m;j++)
if (el[j][]!=i && el[j][]!=i)
addedge(el[j][],el[j][],j),
addedge(el[j][],el[j][],j);
for (int j=;j<=n;j++)
{
if (j==i)continue;
if (!dfn[j])
{
tot++;
root=j;
tarjan(j,j);
}
}
res=max(res,tot+ans);
}
printf("%d\n",res);
}
}
hdu 4587
点双连通分量：同求桥边。网上都说这是边双，根本搞不清楚。这道题主要是细节坑人，其他都没什么。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 10100
#define MAXV MAXN
#define MAXE MAXN*20
#define INF 0x3f3f3f3f
struct Edge
{
int np,id,val;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y,int z,int id)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].id=id;
E[tope].next=V[x];
V[x]=&E[tope];
}
int dfn[MAXN],low[MAXN],top[MAXN],dfstime;
bool edge_vis[MAXE];
int stack[MAXN],tops=-;
vector<int> bridge;
void tarjan(int now)
{
Edge *ne;
low[now]=dfn[now]=++dfstime;
stack[++tops]=now;
for (ne=V[now];ne;ne=ne->next)
{
if (edge_vis[ne->id])continue;
edge_vis[ne->id]=true;
if (dfn[ne->np])
{
low[now]=min(low[now],dfn[ne->np]);
}else
{
tarjan(ne->np);
low[now]=min(low[now],low[ne->np]);
if (low[ne->np]==dfn[ne->np])
{
while (stack[tops]!=ne->np)
top[stack[tops--]]=ne->np;
top[stack[tops--]]=ne->np;
bridge.push_back(ne->id);
}
}
}
} struct edge
{
int x,y,z,id;
}el[MAXE],eb[MAXE];
bool cmp_z(edge e1,edge e2)
{
return e1.z<e2.z;
}
int q[MAXN];
int pnt[MAXN];
int depth[MAXN];
void bfs(int now)
{
int head=-,tail=;
Edge *ne;
q[]=now;
pnt[now]=now;
depth[now]=;
while (head<tail)
{
now=q[++head];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
q[++tail]=ne->np;
depth[ne->np]=depth[now]+;
pnt[ne->np]=now;
}
}
return ;
}
int jump[][MAXN];
void init_lca(int n)
{
for (int i=;i<=n;i++)
jump[][i]=pnt[i];
for (int j=;j<;j++)
for (int i=;i<=n;i++)
jump[j][i]=jump[j-][jump[j-][i]];
}
int lca(int x,int y)
{
if (depth[x]<depth[y])
swap(x,y);
int dep=depth[x]-depth[y];
for (int i=;i<;i++)
if (dep&(<<i))
x=jump[i][x];
if (x==y)return x;
for (int i=;i>=;i--)
if (jump[i][x]!=jump[i][y])
x=jump[i][x],y=jump[i][y];
return pnt[x];
}
int main()
{
freopen("input.txt","r",stdin);
int n,m;
int x,y,z;
while (~scanf("%d%d",&n,&m))
{
memset(V,,sizeof(V));
memset(dfn,,sizeof(dfn));
tope=-;
bridge.clear();
memset(pnt,,sizeof(pnt));
memset(edge_vis,,sizeof(edge_vis));
dfstime=;
for (int i=;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
el[i].x=x;
el[i].y=y;
el[i].z=z;
el[i].id=i;
addedge(x,y,z,i);
addedge(y,x,z,i);
}
for (int i=;i<=n;i++)
{
if (!dfn[i])
{
tarjan(i);
while (~tops)
top[stack[tops--]]=i;
}
}
memset(V,,sizeof(V));
tope=-;
int l=bridge.size();
for (int i=;i<bridge.size();i++)
{
eb[i]=el[bridge[i]];
eb[i].x=top[eb[i].x];
eb[i].y=top[eb[i].y];
addedge(eb[i].x,eb[i].y,,);
addedge(eb[i].y,eb[i].x,,);
}
bfs(top[]);
init_lca(n);
sort(eb,eb+l,cmp_z);
int l2,l1,hh;
int a;
l1=eb[].x,hh=eb[].y;
l2=-;
if (depth[l1]<depth[hh])swap(l1,hh);
int res=-;
for (int i=;i<l;i++)
{
for (int j=;j<;j++)
{
a=j?eb[i].y:eb[i].x;
if (lca(a,l1)==l1)
{
l1=a;
}else if (~l2 && lca(a,l2)==l2)
{
l2=a;
}else if (~l2 && lca(a,l2)==a && lca(a,hh)==hh)
{
//okay
}else if (lca(a,l1)==a && lca(a,hh)==hh)
{
//okay
}else if (lca(a,hh)==a && l2==-)
{
hh=a;
}else if (depth[lca(a,l1)]<=depth[hh] && l2==-)
{
l2=a;
hh=lca(a,l1);
}else
{
res=eb[i].z;
break;
}
}
if (~res)break;
}
printf("%d\n",res);
}
}
hdu 4005