首页 > 其他 > 详细

POJ 2942 Knights of the Round Table 点的双连通分量 + 奇圈

时间:2014-02-17 10:26:26      阅读:306      评论:0      收藏:0      [点我收藏+]

给出一个无向图,然后计算出该图的补图,然后再计算补图中不再任一奇圈内的点的个数。

首先要求出所有的点的双连通分量,然后判断每一个双连通分量中是否存在奇圈,若有,则该双连通分量中的任意一点均在某一个奇圈上。

求解双连通分量的方法:

设 rv[ ] 表示每个点在DFS时被访问的次序,low[ ] 表示节点 u 及其子孙所连接到点中 rv[ ] 最小的值。

首先需要一个辅助栈来存放每一个双连通分量的边。


若边( u , v )仅符合下面两种情况的任意一种则将边压入栈中:

        1,v 尚未被访问。

        2,rv[ v ] <= low[u] 且 v 正在等待回溯。


若当 u 的 子节点 v 回溯完成时有 low[v] >= rv[u],则说明 u 是一个割点,此时要将栈中的在(u , v )及在其后面压入的边弹出,这些边就组成了一个点的双连通分量。


判断奇圈可以用BFS染色法。可见判断二分图的方法


代码有写的好挫。。。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>

#define LL long long
#define ULL unsigned long long
#define PI (acos(-1.0))
#define EPS (1e-10)
#pragma comment(linker,"/STACK:102400000,1024000")

using namespace std;

const int MAX = (1<<30);

struct N
{
    int v,next;
}edge[1001000];

int head[1010];

int Top,Dfs_Clock;

bool Is_Edge[1010][1010],Is_Cut[1010],InCirle[1010],Wait_Dfs[1010];

int rv[1010],low[1010];

void Link(int u,int v)
{
    edge[Top].v = v;
    edge[Top].next = head[u];
    head[u] = Top++;
}

struct E
{
    int u,v;
}te[1001000];

stack<E> st;

int color[1010];

int Top_E;

int Knight;

void dfs(int u,int fa)
{
    rv[u] = Dfs_Clock;
    low[u] = Dfs_Clock++;

    int v;

    for(int p = head[u];p != -1; p = edge[p].next)
    {
        v = edge[p].v;

        E e = (E){u,v};

        if(rv[v] == -1)
        {
            st.push(e);

            dfs(v,u);

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

            if(low[v] >= rv[u])
            {
                Top_E = 0;
                do
                {
                    e = st.top();
                    st.pop();

                    te[Top_E++] = e;
                    
                }while(e.u != u || e.v != v);


                memset(color,-1,sizeof(color));

                color[te[0].u] = 1;
                color[te[0].v] = 0;

                bool mark = false;

                bool Is_Circle = false;

                while(mark == false && Is_Circle == false)
                {

                    mark = true;
                    for(int i = 0;i < Top_E; ++i)
                    {
                        if(color[te[i].u] == -1 && color[te[i].v] != -1)
                        {
                            color[te[i].u] = (color[te[i].v] == 1 ? 0 : 1);
                            mark = false;
                        }
                        else if(color[te[i].u] != -1 && color[te[i].v] == -1)
                        {
                            color[te[i].v] = (color[te[i].u] == 1 ? 0 : 1);
                            mark = false;
                        }
                        else if(color[te[i].u] != -1 && color[te[i].u] ==  color[te[i].v])
                        {
                            Is_Circle = true;
                        }
                    }
                }

                if(Is_Circle)
                {
                    memset(color,-1,sizeof(color));

                    for(int i = 0;i < Top_E; ++i)
                    {
                        if(color[te[i].u] == -1)
                        {
                            color[te[i].u] = 1;
                            {
                                Knight--;
                            }
                            if(InCirle[te[i].u])
                            {
                                Knight++;
                            }
                            else
                            {
                                InCirle[te[i].u] = true;
                            }
                        }

                        if(color[te[i].v] == -1)
                        {
                            color[te[i].v] = 1;
                            {
                                Knight--;
                             }
                            if(InCirle[te[i].v])
                            {
                                Knight++;
                            }
                            else
                            {
                                InCirle[te[i].v] = true;
                            }
                        }
                    }
                }

                Is_Cut[u] = true;
            }
        }
        else if(low[v] <= low[u] && v != fa && Wait_Dfs[v] == false)
        {
            st.push(e);
            low[u] = min(low[u],rv[v]);
        }
    }
    Wait_Dfs[u] = true;
}

int main()
{
    int n,m,i,j,u,v;

    while(scanf("%d %d",&n,&m) && (n||m))
    {
        for(i = 1;i <= n; ++i)
        {
            memset(Is_Edge[i],false,sizeof(bool)*(n+3));
        }

        for(i = 1;i <= m; ++i)
        {
            scanf("%d %d",&u,&v);

            Is_Edge[u][v] = Is_Edge[v][u] = true;
        }

        memset(head,-1,sizeof(int)*(n+3));

        Top = 0;

        for(i = 1;i <= n; ++i)
        {
            for(j = 1;j < i; ++j)
            {
                if(Is_Edge[i][j] == false)
                {
                    Link(i,j);
                    Link(j,i);
                }
            }
        }

        memset(rv,-1,sizeof(int)*(n+3));
        memset(Is_Cut,false,sizeof(bool)*(n+3));
        memset(InCirle,false,sizeof(bool)*(n+3));
        memset(Wait_Dfs,false,sizeof(bool)*(n+3));

        Dfs_Clock = 0;
        Knight = n;

        for(i = 1;i <= n; ++i)
        {
            if(rv[i] == -1)
            {
                dfs(i,-1);
            }
        }
        printf("%d\n",Knight);
    }
    return 0;
}


POJ 2942 Knights of the Round Table 点的双连通分量 + 奇圈

原文:http://blog.csdn.net/zmx354/article/details/19295757

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!