社区讨论

为什么一直RE啊??

SP2878KNIGHTS - Knights of the Round Table参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6uxch2
此快照首次捕获于
2025/11/20 11:13
4 个月前
此快照最后确认于
2025/11/20 11:13
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxN=2000 + 100,maxM=2000000 + 100;
struct Node
{
	int from,to,next;
}edge[maxM*2+1];
int head[maxN+1],low[maxN+1],dfn[maxN+1],n,m,tot,num,cnt;
int id[maxN+1];
int color[maxN+1];
bool G[maxN+1][maxN+1],res[maxN+1];
vector<int> sum[maxN+1];
stack<int> s;
void add(int x,int y)
{
	tot++;
	edge[tot].from=x;
	edge[tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot;
}
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=edge[i].next)
		if(!dfn[edge[i].to]) 
		{
			s.push(i);
			tarjan(edge[i].to,x);
			low[x]=min(low[x],low[edge[i].to]);
			if(dfn[x]<=low[edge[i].to])
			{
				cnt++;
				sum[cnt].clear();
				int k;
				while(1)
				{
					k=s.top();s.pop();
					if(id[edge[k].from]!=cnt) sum[cnt].push_back(edge[k].from);
					if(id[edge[k].to]!=cnt) sum[cnt].push_back(edge[k].to);
					id[edge[k].from]=id[edge[k].to]=cnt;
					if(edge[k].from==x&&edge[k].to==edge[i].to) break;
				}
			}
		}else if(dfn[edge[i].to]<dfn[x]&&edge[i].to!=fa) 
			  {
			  	s.push(i);	
			  	low[x]=min(low[x],dfn[edge[i].to]);
			  }
}
bool check(int x,int pa,int rule)
{
	color[x]=rule;
	for(int i=head[x];i;i=edge[i].next)
		if(edge[i].to!=pa&&id[edge[i].to]==id[x])
		{
			if(color[edge[i].to]==rule) return false;
			if(!check(edge[i].to,x,-rule)&&!color[edge[i].to]) return false;
		}
	return true;
}
void init()
{
	memset(G,false,sizeof(G));
	memset(res,0,sizeof(res));
	memset(edge,0,sizeof(edge));
	memset(color,0,sizeof(color));
	memset(head,0,sizeof(head));
	while(!s.empty()) s.pop();
	tot=0,num=0,cnt=0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(id,0,sizeof(id));
}
void work()
{
	init();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x][y]=G[y][x]=true;
	}
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(!G[i][j]) {add(i,j);add(j,i);}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,0);
	for(int i=1;i<=cnt;i++)
	{
		if(sum[i].size()<3) continue;
 		memset(color,0,sizeof(color));
		if(!check(sum[i][0],0,1))
			for(int j=0;j<sum[i].size();j++)
				res[sum[i][j]]=true;	
	}
	int ans=n;
	for(int i=1;i<=n;i++)
		if(res[i]) ans--;
	printf("%d\n",ans);
}
int main()
{
	while(~scanf("%d%d",&n,&m),n) work(); 
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...