tarjan算法的应用。
还需多练习…….遇上题目还是容易傻住
对于tarjan算法中使用到的Dfn和Low数组.
low[u]:=min(low[u],dfn[v])——(u,v)为后向边，v不是u的子树；
low[u]:=min(low[u],low[v])——(u,v)为树枝边，v为u的子树；
1.求割点：
割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。
原理：若low[v]>=dfn[u],则u为割点。因low[v]>=dfn[u]，则说明v通过子孙无法到达u的祖先。那么对于原图，去掉u后，必然会分成两个子图。
所以处理节点u时，先递归v的子节点，然后回溯至u时，如果满足low[v]>=dfn[u]，则u为割点。
int tarjan(int x)
{
v[x]=1; //点的状态标记，1为已访问，2为割点
Dfn[x]=Low[x]=time++;
for(int i=head[x];i;i=next[i])
{
if(!v[ver[i]])
{
tarjan(ver[i]);
Low[x]=min(Low[x],Low[ver[i]]);
if(Dfn[x]<=low[ver[i]])
v[x]++;
}
else
Low[x]=min(low[x],Dfn[ver[i]]);
if((x==1&&v[x]>2)||(x>1&&v[x]>1)) //对第一个特判
v[x]=2;
else
v[x]=1;
}
} 2.求桥
桥(割边)：删掉它之后，图必然会分裂为两个或两个以上的子图。
原理：若low[v]>dfn[u],则(u,v)为桥。由割点同理可得。但是由于可能存在重边，需要把一条无向边拆成的两条标号相同的有向边，记录每个点的父亲到它的边的标号，如果边(u,v)是v的父亲边，就不能用dfn[u]更新low[v]。这样如果遍历完v的所有子节点后，发现low[v]=dfn[v]，说明u的父亲边(u,v)为割边。
void tarjan(int x)
{
v[x]=1;
Dfn[x]=Low[x]=time++;
for(int i=head[x];i;i=next[i])
{
if(!v[ver[i]])
{
p[ver[i]]=edge[i]; //记录父亲边
tarjan(ver[i]);
Low[x]=min(Low[x],Low[ver[i]]);
}
else if(p[x]!=edge[i]) //不是父亲边则更新
Low[x]=min(Low[x],Dfn[ver[i]]);
if(p[x]&&low[x]==dfn[x])
f[p[x]]=1; //为割边
}
}3.点双连通分量
点双连通分支，在求割点的过程中就能把每个点双连通分支求出。建立一个栈，存储双连通分支。在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。
if(dfn[u]==low[u])
{
scc++;
while(1) //记录每一个点属于的连通块
{
v=sta[top--];
instack[v]=0;
belong[v]=scc; //所取出的点即为双连通分支
if(v==u)
break;
}
}
}4.边双连通分支。在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。
5.一个有桥的连通图，如何把它通过加边变成边双连通图
首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。
统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。
void Tarjan(int u,int fa)
{
int i,v;
low[u]=dfn[u]=++cnt;
sta[++top]=u;
instack[u]=1;
for(i=first[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(i==(fa^1))
continue;
if(!dfn[v])
{
Tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
scc++;
while(1) //记录每一个点属于的连通块
{
v=sta[top--];
instack[v]=0;
belong[v]=scc;
if(v==u)
break;
}
}
}
for(i=1;i<=n;i++)
{
for(j=first[i];j!=-1;j=edge[j].next)
{
v=edge[j].v;
if(belong[i]!=belong[v])
degree[belong[i]]++; //degree为1则为leaf
}
}
int sum=0;
for(i=1;i<=n;i++)
if(degree[i]==1)
sum++; 统计leaf数
}