[POJ 2942] | Eurce's Blog

最近的5天都在研究这一道题目，貌似效率有点低……不过还好最后AC了，作为充实blog的一点体会，也在此稍作记录吧。

一开始是写了一下穷搜，TLE后开始各种想……发现是知识储备不够，于是开始各种读解题报告，随即就读到了双连通分量，tarjan，二分图染色等一系列没听过的东西。BLOG的一个坏处是，知识点总是讲一点不讲一点，甚至有些是直接代码一帖完事。但这篇写得还是挺好的http://blog.csdn.net/lyy289065406/article/details/6756821。

稍微说点题外话，现在做题有个习惯是希望尽量把题目涉及的背景知识面都大致了解一下。之前也把CLRS看了一遍，就是希望自己的知识点不要有太明显的盲点，否则做题时效率实在太低了。但在做有些题的时候，往往认真读了相关定理及证明并实现了书上某个算法后，看题目的discuss却依然一大堆陌生名词。最明显的做网络流时，按照书上写的实现了Edmonds-Karp和Relabel-to-Front算法，也成功解出题目，以为可以和各路神牛做些基本沟通了，结果discuss里一堆dinic、sap什么什么的…………也不知道别人都看的是什么资料。这次这题也有这种感觉，而且真的是不喜欢那种遇到问题再去各种google的方式，感觉就是在打没准备的仗，而且长久下来，知识结构也会变得很零散……刚好这位博主有列出参考书目，也正是大名鼎鼎的黑书了。之前没有选择此书，一是觉得偏竞赛的书籍会较功利，而自己已经不可能全力准备什么比赛了，二是这本书稍微有点老了。但有书看总比一个个BLOG的翻要来得好，还是买回来了。

于是认真读了黑书P285页开始的部分，了解了DFS原来还有各种用法：求连通分量的割点、桥等等。作为对算法思想理解的验证，先A了1523，一道求割点对应分量数目的题目。然后又读了题解中用二分图性质判断奇圈的定理，便开始了各种构思算法实现。这里主要需要解决的问题是，如何保存用DFS找出的双连通分量。一开始我考虑的是在DFS的同时用栈记录当前遍历过的结点，在找到双连通分量时退栈输出结点，WA了数次后发现思路有误。关键在于像：

5 8

3 1

3 5

5 5

4 2

5 3

3 3

4 3

3 4

0 0

这样的数据，栈中会存在不属于当前双连通分量（属于父结点对应的双连通分量）但夹在本双连通分量结点间的结点（好罗嗦……）。于是只能用栈存边，这样出栈的时候，便肯定能得到属于本双连通分量的全部结点了。最后，再考虑了一下具体实现，总算是敲出了这题：

#include<cstdio>
#include<cstring>
using namespace std;

int n,m,d[1001][1001],hd[1001],a[1001],x[1001],el,ck[1001],temp[1001],b[1001],top;

struct edge		//边表
{
    int j,p;
} e[1000000];

struct stk		//边栈，记录当前双连通分量的一个环
{
    int i,j;
} st[1001];

inline void adde(int i,int j)
{
    e[el].j=j;
    e[el].p=hd[i];
    hd[i]=el++;
    e[el].j=i;
    e[el].p=hd[j];
    hd[j]=el++;
}

int CK(int i,int c)		//判断是否为二分图
{
    int j,k,l;
    ck[i]=c;
    for(l=hd[i]; l!=-1; l=e[l].p)
    {
        j=e[l].j;
        if(!b[j]) continue;
        if(ck[j]==-1)
        {
            if(!CK(j,c^1)) return 0;
        }
        else if(ck[j]!=c^1) return 0;
    }
    return 1;
}

void DFS(int i,int f,int d)		//DFS寻找双连通分量，并使用边栈来记录能表示双连通分量中的一个环
{
    int j,k,l;
    a[i]=d;
    for(l=hd[i]; l!=-1; l=e[l].p)
    {
        j=e[l].j;
        if(a[j]==-1)				//若子结点未访问，则记录边的同时深搜遍历
        {
            st[top].i=i;
            st[top].j=j;
            top++;
            DFS(j,i,d+1);
            a[i]=a[i]<a[j]?a[i]:a[j];		//更新最远祖先
            if(d==a[j])		//若为双连通分量，根据栈中的边来构建分量结点集合S，再判断是否为二分图
            {
            	memset(b,0,sizeof b);
            	k=0;
                while(1)
                {
                    --top;
                    temp[k++]=st[top].j;
                    b[st[top].j]=1;
                    if(st[top].i==i) break;
                }
                temp[k++]=i;
                b[i]=1;
                memset(ck,-1,sizeof ck);
                if(!CK(i,0))		//若不为二分图，则置分量中所有结点的标记位为1
                {
                    while(k) x[temp[--k]]=1;
                }
            }
            if(d<a[j]) --top;	//若(i,j)为桥，则令边栈栈顶出栈
        }
        else if(j!=f)		//更新最远祖先
        {
            a[i]=a[i]<a[j]?a[i]:a[j];
        }
    }
}

int main()
{
    int i,j,k,l;
    while(~scanf("%d%d",&n,&m)&&n)
    {
        memset(d,0,sizeof d);
        memset(hd,-1,sizeof hd);
        memset(a,-1,sizeof a);
        memset(x,0,sizeof x);
        el=0;
        while(m--)
        {
            scanf("%d%d",&i,&j);
            d[i][j]=d[j][i]=1;
        }
        for(i=1; i<n; i++)
            for(j=i+1; j<=n; j++)
                if(!d[i][j]) adde(i,j);
        for(i=1,l=0; i<=n; i++)
        {
            top=0;
            if(a[i]==-1) DFS(i,0,1);
            if(!x[i]) l++;
        }
        printf("%d\n",l);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,d[1001][1001],hd[1001],a[1001],x[1001],el,ck[1001],temp[1001],b[1001],top;

struct edge //边表

{

int j,p;

} e[1000000];

struct stk //边栈，记录当前双连通分量的一个环

{

int i,j;

} st[1001];

inline void adde(int i,int j)

{

e[el].j=j;

e[el].p=hd[i];

hd[i]=el++;

e[el].j=i;

e[el].p=hd[j];

hd[j]=el++;

}

int CK(int i,int c) //判断是否为二分图

{

int j,k,l;

ck[i]=c;

for(l=hd[i]; l!=-1; l=e[l].p)

{

j=e[l].j;

if(!b[j]) continue;

if(ck[j]==-1)

{

if(!CK(j,c^1)) return 0;

}

else if(ck[j]!=c^1) return 0;

}

return 1;

}

void DFS(int i,int f,int d) //DFS寻找双连通分量，并使用边栈来记录能表示双连通分量中的一个环

{

int j,k,l;

a[i]=d;

for(l=hd[i]; l!=-1; l=e[l].p)

{

j=e[l].j;

if(a[j]==-1) //若子结点未访问，则记录边的同时深搜遍历

{

st[top].i=i;

st[top].j=j;

top++;

DFS(j,i,d+1);

a[i]=a[i]<a[j]?a[i]:a[j]; //更新最远祖先

if(d==a[j]) //若为双连通分量，根据栈中的边来构建分量结点集合S，再判断是否为二分图

{

memset(b,0,sizeof b);

k=0;

while(1)

{

--top;

temp[k++]=st[top].j;

b[st[top].j]=1;

if(st[top].i==i) break;

}

temp[k++]=i;

b[i]=1;

memset(ck,-1,sizeof ck);

if(!CK(i,0)) //若不为二分图，则置分量中所有结点的标记位为1

{

while(k) x[temp[--k]]=1;

}

if(d<a[j]) --top; //若(i,j)为桥，则令边栈栈顶出栈

}

else if(j!=f) //更新最远祖先

{

a[i]=a[i]<a[j]?a[i]:a[j];

}

int main()

{

int i,j,k,l;

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

{

memset(d,0,sizeof d);

memset(hd,-1,sizeof hd);

memset(a,-1,sizeof a);

memset(x,0,sizeof x);

el=0;

while(m--)

{

scanf("%d%d",&i,&j);

d[i][j]=d[j][i]=1;

}

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

for(j=i+1; j<=n; j++)

if(!d[i][j]) adde(i,j);

for(i=1,l=0; i<=n; i++)

{

top=0;

if(a[i]==-1) DFS(i,0,1);

if(!x[i]) l++;

}

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

}

return 0;

}

虽然AC，但是g++跑了1100ms++，status上神牛们则是100ms左右……估计是递归验证二分图的那步效率太低了，但一时也想不到怎样改进比较好（而且实在不喜欢看别人的代码……）。以后有新思路了再来改进吧～