> #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);
> 	}
> }


退栈的时候退掉y后就退出。第一次写真是写脑残了，4个半小时我擦擦擦啊

• 自己献上数据 (378) 511818218 2013-09-26 21:28:54
  • Re:自己献上数据 (531) forestgump2012 2022-05-11 21:55:15