关于基础知识的预备桥和割点、双联通分量、强连通分量，支配树。（并不会支配树）
关于有向图的Tarjan，是在熟悉不过的了，它的主要功能就是求强联通分量，缩个点，但是要注意一下构建新图的时候有可能出现重边（即使原图没有重边），他还时常和拓扑排序放在一起。eg：
#include<cstdio>
#include<cstring>
#include<algorithm>
char xB[(<<)+],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &x){
register char ch=gtc;
for(x=;ch<''||ch>'';ch=gtc);
for(;ch>=''&&ch<='';x=(x<<)+(x<<)+ch-'',ch=gtc);
}
const int N=;
const int M=;
struct V{int to,next;}c[M<<];
int head[N],e[N],t;
inline void add(int x,int y,int *id){
c[++t].to=y,c[t].next=id[x],id[x]=t;
}
int dfn[N],low[N],Ti,belong[N],stack[N],top,num,size[N];
bool in[N];
int n,m;
int f[N],sum[N],degree[N];
int q[N],front=,tail;
int ans,fin,P;
int visit[N];
inline void Tarjan(int x){
dfn[x]=low[x]=++Ti,in[x]=true,stack[++top]=x;
for(int i=head[x];i;i=c[i].next)
if(dfn[c[i].to]==)
Tarjan(c[i].to),low[x]=std::min(low[x],low[c[i].to]);
else if(in[c[i].to])
low[x]=std::min(low[x],dfn[c[i].to]);
if(low[x]==dfn[x]){
int j;++num;
do{
j=stack[top--],in[j]=false,belong[j]=num,++size[num];
}while(j!=x);
}
}
int main(){
read(n),read(m),read(P);
for(int i=,x,y;i<=m;++i)
read(x),read(y),add(x,y,head);
for(int i=;i<=n;++i)
if(dfn[i]==)Tarjan(i);
for(int x=;x<=n;++x)
for(int i=head[x];i;i=c[i].next)
if(belong[x]!=belong[c[i].to])
add(belong[x],belong[c[i].to],e),++degree[belong[c[i].to]];
for(int i=;i<=num;++i){
if(degree[i]==)q[++tail]=i;
sum[i]=;
}
while(front<=tail){
int x=q[front++];
f[x]+=size[x];
if(f[x]>ans)ans=f[x],fin=sum[x];
else if(f[x]==ans)fin=(fin+sum[x])%P;
for(int i=e[x];i;i=c[i].next){
--degree[c[i].to];
if(visit[c[i].to]!=x){
if(f[x]>f[c[i].to])f[c[i].to]=f[x],sum[c[i].to]=sum[x];
else if(f[x]==f[c[i].to])sum[c[i].to]=(sum[c[i].to]+sum[x])%P;
visit[c[i].to]=x;
}
if(degree[c[i].to]==)q[++tail]=c[i].to;
}
}
printf("%d\n%d",ans,fin);
return ;
}
【BZOJ 1093】[ZJOI2007]最大半连通子图
（在有向图的Tarjan里面还有支配树，表示这个坑过了联赛再补。）
对于无向图的Tarjan就广泛得多了，首先桥和边双，以及割点和点双。
关于桥就是他的防重边打法（就是记录父亲边而不是父亲，这样效率不仅高而且还防重边）。eg：
#include<cstdio>
#include<cstring>
#include<algorithm>
char xB[(<<)+],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &sum){
register char ch=gtc;
for(sum=;ch<''||ch>'';ch=gtc);
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=gtc);
}
const int N=;
struct V{int to,next,id;}c[N<<];
int head[N],t;
inline void add(int x,int y,int z){
c[++t].to=y,c[t].next=head[x],c[t].id=z,head[x]=t;
}
int soa[N],sob[N];
int dfn[N],low[N],Ti;
bool is[N];
int n,m,k,l,s;
inline void Tarjan(int x,int OPai){
dfn[x]=low[x]=++Ti;
for(int i=head[x];i;i=c[i].next)
if(dfn[c[i].to]==)
Tarjan(c[i].to,c[i].id),
soa[x]+=soa[c[i].to],sob[x]+=sob[c[i].to],
low[x]=std::min(low[x],low[c[i].to]);
else if(c[i].id!=OPai)
low[x]=std::min(low[x],dfn[c[i].to]);
if(low[x]==dfn[x]&&(soa[x]==||sob[x]==||soa[x]==k||sob[x]==l))
is[OPai]=true,++s;
}
int main(){
//freopen("read.in","r",stdin);
read(n),read(m),read(k),read(l);
for(int i=,x;i<=k;++i)
read(x),soa[x]=;
for(int i=,x;i<=l;++i)
read(x),sob[x]=;
for(int i=,x,y;i<=m;++i)
read(x),read(y),add(x,y,i),add(y,x,i);
Tarjan(,);
printf("%d\n",s-);
for(int i=;i<=m;++i)
if(is[i])
printf("%d\n",i);
return ;
}
【vijos 1769】网络的关键边
对于边双我并没有打过题，有一种是记录栈然后跳栈（并不知道怎么打），但是有一种更好打的就是先求桥并记录然后在dfs一遍求各个边双。
然后就是割点了，这个比较好求，在这里主要是体现了对于dfs树的利用，这就涉及到Tarjan算法本身原理了，这里就有一道dfs树上利用割点的树归：
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N=;
const int M=;
char xB[(<<)+],*xS=xB,*xTT=xB;
#define gtc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
inline void read(int &sum){
register char ch=gtc();
for(sum=;ch<''||ch>'';ch=gtc());
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=gtc());
}
struct V{int to,next;}c[M<<];
int head[N],t;
inline void add(int x,int y){
c[++t].to=y,c[t].next=head[x],head[x]=t;
}
int dfn[N],low[N],size[N],Ti;
LL ans[N];
int n,m;
inline void Tarjan(int x){
dfn[x]=low[x]=++Ti,size[x]=;
for(int i=head[x],cnt=n-;i;i=c[i].next)
if(!dfn[c[i].to]){
Tarjan(c[i].to),size[x]+=size[c[i].to];
low[x]=std::min(low[x],low[c[i].to]);
if(low[c[i].to]>=dfn[x])
cnt-=size[c[i].to],ans[x]+=(LL)size[c[i].to]*cnt*;
}else low[x]=std::min(low[x],dfn[c[i].to]);
}
int main(){
read(n),read(m);
for(int i=,x,y;i<=m;++i)
read(x),read(y),add(x,y),add(y,x);
for(int i=,temp=(n-)<<;i<=n;++i)
ans[i]=temp;
Tarjan();
for(int i=;i<=n;++i)printf("%lld\n",ans[i]);
return ;
}
【BZOJ 1123】[POI2008]BLO
还有一个板子题：
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=;
char xB[(<<)+],*xS=xB,*xTT=xB;
#define gtc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
inline void read(int &sum){
register char ch=gtc();
for(sum=;ch<''||ch>'';ch=gtc());
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=gtc());
}
struct V{int to,next;}c[N<<];
int head[N],t;
inline void add(int x,int y){
c[++t].to=y,c[t].next=head[x],head[x]=t;
}
int low[N],dfn[N],Ti;
bool is[N];
int degree[N];
int n,m;
int ans[N];
inline void Tarjan(int x){
low[x]=dfn[x]=++Ti;int cnt=;
for(int i=head[x];i;i=c[i].next)
if(dfn[c[i].to]==){
Tarjan(c[i].to);
low[x]=std::min(low[x],low[c[i].to]);
if(low[c[i].to]>=dfn[x])++cnt;
}else low[x]=std::min(low[x],dfn[c[i].to]);
if((x==&&cnt>=)||(x!=&&cnt>=))is[x]=true;
}
int main(){
read(n),read(m);
for(int i=,x,y;i<=m;++i){
read(x),read(y);
add(x,y),add(y,x);
++degree[x],++degree[y];
}
Tarjan();
for(int i=;i<=n;++i)
if(is[i]==false&&n-+degree[i]==m)
ans[++ans[]]=i;
printf("%d\n",ans[]);
for(int i=;i<=ans[];++i)
printf("%d ",ans[i]);
return ;
}
UOJ #67. 新年的毒瘤
关于点双，网上大多数人都说他必须栈内存边，他们只关注于一个点会存在于多个点双，并没有去解决他，但是我想说可以存点！！！
首先我们先证明一件事，就是一个点双内的点在dfs树上一定是一段连续的简单路径。（我们只考虑连通图）证明：第一，对于一个无向连通图，如果把他的点双变成点原来的点只留下割点并保持原来的连通性，那么这张图一定是一棵树，那么在各个点双内部一定是这棵dfs树的一部分其内部与外界只有割点保持联通，第二，对于一个点双内部的点与树边所形成的结构不可能出现叉型结构，如果出现叉，首先这个叉的分支一定有一个是来源，其他是回溯产物，而叉至少有三个分支，所以回溯产物至少有两个，但是其中一个在回到原点之前一定会访问另外的分支，因此不成立，综上，一个点双内的点在dfs树上一定是一段连续的简单路径。
那么我们现在就是有一群简单路径，如果我们将点入栈，出栈时一直pop到本节点，那么就会出现一系列的错误，因为栈里的点不全是本点双内的点，但是如果我们pop到这次连向的点并另外加入本点的话，就不会出现这样的问题，因为首先我们递归下去，最小的枝杈（就是他只有深度最小的点与其他点双有联系）一定会被完整pop如此递归下去所有的点都会去他应在的点双。
这样的作法我已经A了三道题，有一道是一道NOIP模拟题就不在这里呈现。
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
char xB[(<<)+],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &sum){
register char ch=gtc;
for(sum=;ch<''||ch>'';ch=gtc);
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=gtc);
}
const int N=;
const int M=;
int ans[N],Ti;
int dis[M],num;
int stack[N],top;
int f[M],ote[M];
inline int find(int x){
return f[x]==x?x:(f[x]=find(f[x]));
}
int dfn[N],low[N];
struct V{int to,next;}c[M<<];
int head[M],q[M],e[N],t;
inline void add(int x,int y,int *id){
c[++t].to=y,c[t].next=id[x],id[x]=t;
}
bool v[M];
int n,m,Q,rt;
inline void Tarjan(int x){
int cnt=;
low[x]=dfn[x]=++Ti,stack[++top]=x;
for(int i=e[x];i;i=c[i].next)
if(dfn[c[i].to]==){
Tarjan(c[i].to);
low[x]=std::min(low[x],low[c[i].to]);
if(low[c[i].to]>=dfn[x]){
int j;++num;
do{
j=stack[top--],add(j,num+n,head),add(num+n,j,head);
}while(j!=c[i].to);
add(x,num+n,head),add(num+n,x,head);
++cnt;
}
}else low[x]=std::min(low[x],dfn[c[i].to]);
if(x==){
if(cnt>=)rt=;
else rt=num;
}
}
inline void Tarjan(int x,int fa){
f[x]=x,ote[x]=fa;
for(int i=head[x];i;i=c[i].next)
if(c[i].to!=fa)
Tarjan(c[i].to,x),f[c[i].to]=x;
v[x]=true;
for(int i=q[x];i;i=c[i].next)
if(v[c[i].to])
--dis[find(c[i].to)],--dis[ote[find(c[i].to)]];
}
inline void dfs(int x,int fa){
for(int i=head[x];i;i=c[i].next)
if(c[i].to!=fa)
dfs(c[i].to,x),dis[x]+=dis[c[i].to];
if(x<=n)ans[x]=dis[x];
}
int main(){
//freopen("read.in","r",stdin);
read(n),read(m),read(Q);
for(int i=,x,y;i<=m;++i)
read(x),read(y),add(x,y,e),add(y,x,e);
Tarjan();
for(int i=,x,y;i<=Q;++i)
read(x),read(y),add(x,y,q),add(y,x,q),++dis[x],++dis[y];
Tarjan(rt,);
dfs(rt,);
for(int i=;i<=n;++i)
printf("%d\n",ans[i]);
return ;
}
【BZOJ 3331】[BeiJing2013]压力
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ft first
#define sd second
#define pb push_back
#define mmp(a,b) (std::make_pair(a,b))
#define mid ((l+r)>>1)
#define newnode (node+(sz++))
char xB[(<<)+],*xS=xB,*xTT=xB;
#define gtc (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
inline void read(int &sum){
register char ch=gtc;
for(sum=;ch<''||ch>'';ch=gtc);
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=gtc);
}
typedef std::pair<int,int> pii;
const int N=;
const int Inf=0x3f3f3f3f;
std::set<pii> st[N];
int dfn[N],low[N],stack[N],top,Ti,min[N],num;
bool is[N];
int size[N<<],height[N<<],f[N<<],anc[N<<],deep[N<<],id[N<<],anti[N<<];
int len;
int n,m,q;
int val[N<<];
struct V{int to,next;}c[N<<];
int head[N],t,to[N<<];
std::vector<int> mem;
inline void add(int x,int y,int *name){
c[++t].to=y,c[t].next=name[x],name[x]=t;
}
inline void Tarjan(int x){
dfn[x]=low[x]=++Ti,stack[++top]=x;
for(int i=head[x];i;i=c[i].next)
if(dfn[c[i].to]==){
deep[c[i].to]=deep[x]+;
Tarjan(c[i].to),low[x]=std::min(low[x],low[c[i].to]);
if(low[c[i].to]>=dfn[x]){
int j;
min[++num]=x;
mem.clear(),mem.pb(x);
do{
j=stack[top--],mem.pb(j);
if(deep[j]<deep[min[num]])
min[num]=j;
}while(j!=c[i].to);
for(j=;j<mem.size();++j)
if(mem[j]==min[num])
add(min[num],num+n,to),f[num+n]=min[num];
else
add(num+n,mem[j],to),f[mem[j]]=num+n,st[num].insert(mmp(val[mem[j]],mem[j]));
val[num+n]=st[num].begin()->ft;
}
}else low[x]=std::min(low[x],dfn[c[i].to]);
}
inline void dfs(int x){
size[x]=,deep[x]=deep[f[x]]+;
for(int i=to[x];i;i=c[i].next){
dfs(c[i].to);
size[x]+=size[c[i].to];
if(size[c[i].to]>size[height[x]])
height[x]=c[i].to;
}
}
inline void dfs(int x,int tp){
id[x]=++len,anti[len]=x,anc[x]=tp;
if(height[x])dfs(height[x],tp);
for(int i=to[x];i;i=c[i].next)
if(c[i].to!=height[x])
dfs(c[i].to,c[i].to);
}
struct Segment_Tree{
Segment_Tree *ch[];
int min;
}*root,node[N<<];
int sz;
inline void build(Segment_Tree *&p,int l,int r){
p=newnode;
if(l==r){
p->min=val[anti[l]];
return;
}
build(p->ch[],l,mid);
build(p->ch[],mid+,r);
p->min=std::min(p->ch[]->min,p->ch[]->min);
}
inline void U(Segment_Tree *p,int l,int r,int pos,int key){
if(l==r){p->min=key;return;}
if(pos<=mid)U(p->ch[],l,mid,pos,key);
else U(p->ch[],mid+,r,pos,key);
p->min=std::min(p->ch[]->min,p->ch[]->min);
}
inline int Q(Segment_Tree *p,int l,int r,int z,int y){
if(z<=l&&r<=y)return p->min;
int ret=Inf;
if(z<=mid)ret=std::min(ret,Q(p->ch[],l,mid,z,y));
if(mid<y)ret=std::min(ret,Q(p->ch[],mid+,r,z,y));
return ret;
}
inline int Q(int x,int y){
int ret=Inf;
while(anc[x]!=anc[y]){
if(deep[anc[x]]<deep[anc[y]])std::swap(x,y);
ret=std::min(ret,Q(root,,len,id[anc[x]],id[x]));
x=f[anc[x]];
}
if(deep[x]<deep[y])std::swap(x,y);
ret=std::min(ret,Q(root,,len,id[y],id[x]));
if(y>n)ret=std::min(ret,val[f[y]]);
return ret;
}
inline bool check(){
register char ch=gtc;
while(ch!='C'&&ch!='A')ch=gtc;
return ch=='C';
}
int main(){
read(n),read(m),read(q);
for(int i=;i<=n;++i)read(val[i]);
for(int i=,x,y;i<=m;++i)
read(x),read(y),add(x,y,head),add(y,x,head);
Tarjan(),dfs(),dfs(,),build(root,,len);
for(int i=,x,y;i<=q;++i){
if(check()){
read(x),read(y);
U(root,,len,id[x],y);
if(x==){val[x]=y;continue;}
st[f[x]-n].erase(mmp(val[x],x));
st[f[x]-n].insert(mmp(y,x));
val[f[x]]=st[f[x]-n].begin()->ft;
U(root,,len,id[f[x]],val[f[x]]);
val[x]=y;
}else{
read(x),read(y);
printf("%d\n",Q(x,y));
}
}
}
codeforces Round #278 E Tourists
这两道题反映出一个点双建图的一般思路，就是对一个点双建一个点，这个点双内部深度最小的点当做其父亲其余为其儿子，这样的话在新树上的两点之间的路径会经过他们之间的点双和割点，而且有的时候要特殊处理lca节点。
在真正打点双之前我一直觉得建图方法是“把他的点双变成点原来的点只留下割点并保持原来的连通性”，我不知道这样建图会不会有一天排上用场，只是目前的题目都用上面的做法解决得十分顺手。