LCA的tarjan算法的理解
粒子群优化算法演示

poj 2117 求割点的tarjan算法

scturtle posted @ 2011年10月20日 17:43 in algorithm , 5108 阅读

大四真闲,也不突击比赛了,可以拿出大把的时间慢慢看点儿算法,研究一下证明,tarjan大神的三个图论算法总算是都了解了。

割点是无向图中去掉后能把图割开的点。dfs时用dfn(u)记录u的访问时间,用low(u)数组记录u和u的子孙能追溯到的最早的节点(dfn值最小)。由于无向图的dfs只有回边和树边,且以第一次dfs时的方向作为边的方向,故有:
low=min{
dfn(u),
dfn(v),若(u,v)为回边(非树边的逆边)
low(v),若(u,v)为树边
}

顶点u是割点当且仅当其满足(1)或者(2):
(1) 若u是树根,且u的孩子数sons>1。因为没有u后,以这些孩子为根的子树间互相就不连通了,所以去掉u后得到sons个分支。
(2) 若u不是树根,且存在树边(u,v)使 low(v)>=dfn(u)。low值说明以v为根的子树不能到达u的祖先也就是去掉u后不能和原图联通,所以得到{这样的v的个数+1}个分支。

这个题是求无向图(不一定联通)中,去掉一个顶点可以形成的最多的分支数,对所有分支tarjan一下就知道了去掉哪个多了,注意孤立点的情况。求low时其实不用判断树边的逆边的情况,仔细琢磨一下,对结果没有影响,又能省很多代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn];
int dfn[maxn],low[maxn];
bool vit[maxn];
int n,idx,sons;
int ans;

void dfs(int u,bool root)
{
    vit[u]=1;
    dfn[u]=low[u]=++idx;
    int child=0;
    for(it i=g[u].begin();i!=g[u].end();++i)
    {
        int v=*i;
        if(!dfn[v])
        {
            dfs(v,false);
            low[u]=min(low[u],low[v]);
            if(root)
                sons++;
            else if(low[v]>=dfn[u])
                child++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    ans=max(ans,child+1);
}

int tarjan(int root)
{
    if(g[root].size()==0) return 0;
    memset(dfn,0,sizeof(dfn));
    ans=idx=sons=0;
    dfs(root,true);
    if(sons>1) ans=max(ans,sons);
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,u,v;
    while(scanf("%d%d",&n,&m)!=EOF && n)
    {
        for(int i=0;i<n;i++)
            g[i].clear();
        while(m-->0)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(vit,0,sizeof(vit));
        int ma=0,total=0;
        for(int i=0;i<n;i++)
            if(!vit[i])
                total++,ma=max(ma,tarjan(i));
        printf("%d\n",total+ma-1);
    }
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter