POJ 2942 圆桌骑士问题。

Description

Input

Output

Sample Input

5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output

2

Hint

Huge input file, ‘scanf‘ recommended to avoid TLE.

题意不说了，经典问题。

解题思路:主要是奇圈的判断，由于二分图与奇圈恰好相对，所以对每一个圈判断二分图，最后统计即可。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014/1/18 18:00:02
File Name :F.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=3000;
int head[maxn],dfn[maxn],mark[maxn],odd[maxn],Stack[maxn],tol,indexx,top,col[maxn],low[maxn];
int n;
struct node 
{
      int next,to;
}edge[1000000];
void add(int u,int v)
{
      edge[tol].to=v;
      edge[tol].next=head[u];
      head[u]=tol++;
}
bool judge(int s)
{
      memset(col,-1,sizeof(col));
      int cnt=0;
      for(int i=1;i<=n;i++)cnt+=mark[i];
      if(cnt<3)return 1;
      queue<int> q;
      q.push(s);
      col[s]=0;
      while(!q.empty())
      {
	     int u=q.front();
	     q.pop();
	     for(int i=head[u];i!=-1;i=edge[i].next)
	     {
		    int v=edge[i].to;
		    if(!mark[v])continue;
		    if(col[v]==col[u])
			   return 0;
		    if(col[v]==-1)
		    {
			   col[v]=1-col[u];
			   q.push(v);
		    }
	     }
      }
      return 1;
}
void fun(int u)
{
      if(judge(u)==0)
      {
	     for(int i=1;i<=n;i++)
		    if(mark[i])
			   odd[i]=1;
      }
}
void tarjin(int u,int pre)
{
      low[u]=dfn[u]=++indexx;
      Stack[top++]=u;
      int v;
      for(int i=head[u];i!=-1;i=edge[i].next)
      {
	     int v=edge[i].to;
	     if(v==pre)continue;
	     if(!dfn[v])
	     {
                   tarjin(v,u);
		     if(low[u]>low[v])
			    low[u]=low[v];
		     if(low[v]>=dfn[u])
		     {
			    memset(mark,0,sizeof(mark));
			    int vn;
			    do
			    {
				   vn=Stack[--top];
				   mark[vn]=1;
			    }while(vn!=v);
			    mark[u]=1;
			    fun(u);
		     }
	     }
	     else if(low[u]>dfn[v])
		    low[u]=dfn[v];
      }
}
int mp[2000][2000];
int main()
{
      //freopen("data.in","r",stdin);
      //freopen("data.out","w",stdout);
      int i,j,k,m;
      while(~scanf("%d%d",&n,&m))
      {
	     if(n==0&&m==0)break;
	     memset(head,-1,sizeof(head));tol=0;
	     memset(dfn,0,sizeof(dfn));
            memset(odd,0,sizeof(odd));
	     for(i=1;i<=n;i++)
		    for(j=1;j<=n;j++)
			   mp[i][j]=1;
	     while(m--)
	     {
		    scanf("%d%d",&i,&j);
		    mp[i][j]=mp[j][i]=0;
	     }
	     for(i=1;i<=n;i++)
		    for(j=i+1;j<=n;j++)
			   if(mp[i][j])
				  add(i,j),add(j,i);
	     indexx=top=0;
	     for(i=1;i<=n;i++)
		    if(!dfn[i])
			   tarjin(i,i);
            int ans=0;
	     for(i=1;i<=n;i++)
		    if(!odd[i])
			   ans++;
	     printf("%d\n",ans);
      }
      return 0;
}

POJ 2942 圆桌骑士问题。

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18456277