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

const int N=3000115,M=2005;
int tot,C,p,n,m,ans,head[M],next[N],ver[N],dfn[M],low[M],num,stack[M],sat[M][M],col[M],q[M],g[M];
bool v[M],in[M],map[M][M];

void add(int x,int y)
{
	ver[++tot]=y;next[tot]=head[x];head[x]=tot;
	ver[++tot]=x;next[tot]=head[y];head[y]=tot;
}

void tarjan(int x,int parent)
{
	dfn[x]=low[x]=++num;
	stack[++p]=x;
	int i,y;
	for(i=head[x];i!=-1;i=next[i])
	{
		if(ver[i]==parent) continue;
		if(dfn[y=ver[i]])
		{
			low[x]=min(low[x],dfn[y]);
			continue;
		}
		if(!dfn[y])
		{
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
		}
		if(dfn[x]<=low[y])
		{
			sat[++C][0]=1;
			sat[C][sat[C][0]]=x;
			while(1)
			{
				y=stack[p--];
				if(y==x){p++;break;}
				sat[C][++sat[C][0]]=y;
			}
		} 
	}
}

void check(int x)
{
	bool flag=0;
	int i,a,b,l,r;
	memset(in,0,sizeof(in));
	memset(col,-1,sizeof(col));
	memset(g,-1,sizeof(g));
	for(i=1;i<=sat[x][0];i++) in[sat[x][i]]=1;
	q[l=r=0]=sat[x][1];
	col[q[l]]=1;
	while(l<=r)
	{
		a=q[l++];
		for(i=head[a];i!=-1;i=next[i])
		{
			if(ver[i]==g[l-1]) continue;
			if(in[b=ver[i]])
			{
				if(col[b]==-1)
				{
					col[b]=col[a]^1;
					q[++r]=b;
					g[r]=a;
				}
				else if(col[b]==col[a])
				{
					flag=1;
					break;
				}
			}
		}
		if(flag) break;
	}
	//cout<<x<<' '<<flag<<endl;
	if(flag)
	{
		for(i=1;i<=sat[x][0];i++) 
			v[sat[x][i]]=1;
	}
}

int main()
{
	int i,j,x,y;
	while(scanf("%d%d",&n,&m)&&n&&m)
	{
		memset(head,-1,sizeof(head));
		memset(v,0,sizeof(v));
		memset(map,0,sizeof(map));
		memset(dfn,0,sizeof(dfn));//= =我用dfn做判断条件忘了清了 
		memset(low,0,sizeof(low));
		memset(sat,0,sizeof(sat));
		memset(stack,0,sizeof(stack)); 
		tot=-1;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			map[x][y]=map[y][x]=1;
		}
		for(i=2;i<=n;i++)
			for(j=i-1;j;j--)
				if(!map[i][j])
					add(i,j);
		p=C=num=ans=0;
		for(i=1;i<=n;i++)
			if(!dfn[i])
				tarjan(i,-1);
	/* 
		for(i=1;i<=C;i++)
		{
			for(j=1;j<=sat[i][0];j++)
				cout<<sat[i][j]<<' ';
			puts("");
		}
	*/ 
		for(i=1;i<=C;i++)
			check(i);
		for(i=1;i<=n;i++)
			if(!v[i]) ans++;
		printf("%d\n",ans);
	}
}

• Re:求能卡掉这代码的数据 (6) humanfy 2013-09-26 15:07:40
• Re:求能卡掉这代码的数据 (2581) 511818218 2013-09-26 21:27:50
  • 自己献上数据 (378) 511818218 2013-09-26 21:28:54
    • Re:自己献上数据 (531) forestgump2012 2022-05-11 21:55:15