POJ 1236 Network of Schools（tarjan算法 + LCA）

　　这个题目网上有很多答案，代码也很像，不排除我的。大家的思路应该都是taijan求出割边，然后找两个点的LCA（最近公共祖先），这两个点和LCA以及其他点构成了一个环，我们判断这个环上的割边有几条，我们的答案就少几个。

　　有人问，这个题重边怎么办呢，重边肯定不是桥啊。额……对于这个我只能说，这个题的原始图应该是没有重边的，后来加的边可能会有重边，不过不影响我们的判断，因为我们通过标记点的方式去判的。（这个题还是应该说明一下啊，题目有点问题……）。

　　其次，这个题的好玩之处来了，网上人分享的代码，居然过不了一组很简单的样例（如下），（现在大多人可能已经修正了），其实这个原因我应该是找到了，那就是dfn（出生日期）和deep（深搜的层数）的使用错误，当你使用deep的时候交换两者的值是没错的，因为我们总能让他们调整到一层上，然后他们的LCA也一定在一层上了，使用fa数组可以追溯到他们的LCA。然而如果是用dfn交换两者的值就是错误的了，因为即使你调整了他们的值满足一定的大小关系，他们也不一定在一层上，很有可能追溯到了环的外面，所以在追溯的时候很可能会多减上几条边。也就是出现了下面的样例，答案是1，有人输出了0；

　　其实这个地方我一直有一个疑惑，那就是使用dfn判断的时候，最后的时候居然会出现二者不相等的情况，这与深搜的性质相违背，到现在也没找到一个样例可以说明他是正确的，我确实感觉到当判断完前两个循环的时候dfn【u】就是他们的LCA了，这个疑惑我先放到这里，便于以后解答，在以后我会主要选择记录深度的方法去做，比较好理解，比较保险（就如我下面代码里的方法）

　　附：这个题还有一个解决方法，就是求双连通分量，通过判断两点是否在一个分量里判断两点之间的边是否为桥，然后再合并这两个点。求连通分量的办法一种是并查集，在判断的时候合并到一个集合里，一种是栈的储存方式，id数组，与有向图求强连通分量的方法一致。注意无向图的双连通分量不是指能否相互到达，而是指这个分量里面不含桥，所以当两个点不在一个集合中的时候，这条边一定就是桥。

6 5
1 2
2 3
2 4
3 5
4 6
1
5 6

答案：1

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 100010

int head[maxn],dfn[maxn],low[maxn],fa[maxn],deep[maxn];

int all,tot,bridge[maxn],brinum;

struct Edge

{

    int to,nxt;

} edge[*maxn];

void addadge(int a,int b)

{

    edge[tot].to = b;

    edge[tot].nxt = head[a];

    head[a] = tot++;

}

void dfs(int u,int pa)

{

    low[u] = dfn[u] = ++all;

    deep[u] = deep[pa] + ;

    for(int i = head[u]; i != -; i = edge[i].nxt)

    {

        int v = edge[i].to;

        if(!dfn[v])

        {

            fa[v] = u;

            dfs(v,u);

            low[u] = min(low[u],low[v]);

            if(low[v] > dfn[u])

            {

                bridge[v] = ;

                brinum++;

            }

        }

        else if(v != pa) low[u] = min(low[u],dfn[v]);

    }

}

void lca(int a,int b)

{

    while(deep[a] > deep[b])

    {

        if(bridge[a])

        {

            bridge[a] = ;

            brinum--;

        }

        a = fa[a];

    }

    while(deep[b] > deep[a])

    {

        if(bridge[b])

        {

            bridge[b] = ;

            brinum--;

        }

        b = fa[b];

    }

    while(a != b)

    {

        if(bridge[a])

        {

            bridge[a] = ;

            brinum--;

        }

        if(bridge[b])

        {

            bridge[b] = ;

            brinum--;

        }

        a = fa[a];

        b = fa[b];

    }

}

int main()

{

    int n,m,q,a,b,ca = ;

    while(~scanf("%d%d",&n,&m))

    {

        if(!n && !m) break;

        for(int i = ; i <= n; i++)

        {

            head[i] = -;

            dfn[i] = ;

            low[i] = ;

            fa[i] = i;

            deep[i] = ;

            bridge[i] = ;

        }

        tot = ;

        all = ;

        brinum = ;

        for(int i = ; i < m; i++)

        {

            scanf("%d%d",&a,&b);

            addadge(a,b);

            addadge(b,a);

        }

        dfs(,);

        scanf("%d",&q);

        printf("Case %d:\n",++ca);

        while(q--)

        {

            scanf("%d%d",&a,&b);

            lca(a,b);

            printf("%d\n",brinum);

        }

        puts("");

    }

    return ;

}

巴特西

POJ 1236 Network of Schools（tarjan算法 + LCA）

最新文章

热门文章