社区讨论
为什么一直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 条回复,欢迎继续交流。
正在加载回复...