社区讨论
4AC 7WA 蒟蒻求助
P3388【模板】割点(割顶)参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6zkk6c
- 此快照首次捕获于
- 2025/11/20 13:23 4 个月前
- 此快照最后确认于
- 2025/11/20 13:23 4 个月前
40分求助
CPP#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 100001
#define M 2000001
#define INF 0x7fffffff
using namespace std;
struct Edge{
int v,next;
}edge[2*M];
int n,m,s;
int head[N],cnt;
int dfn[N],low[N],Index,ans;
bool flag[N];
inline int Min(int a,int b){
return a>b?b:a;
}
inline int read(void){
int x(0),f(1);
char ch(getchar());
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-f;
for(;isdigit(ch);ch=getchar())
x=(x<<3)+(x<<1)+ch-48;
return x*f;
}
inline void addEdge(int u,int v){
edge[++cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}
//简单粗暴取名法2333
void cutNode(int cur,int father){
int child(0);
dfn[cur]=low[cur]=++Index;
for(int i=head[cur];i!=-1;i=edge[i].next){
if(dfn[edge[i].v]==0){
child++;
cutNode(edge[i].v,cur);
low[cur]=Min(low[cur],low[edge[i].v]);
if(cur!=s && dfn[cur]<=low[edge[i].v])
flag[cur]=true,ans++;
else if(cur==s && child>=2)
flag[cur]=true,ans++;
}
else if(edge[i].v!=father){
low[cur]=Min(low[cur],dfn[edge[i].v]);
}
}
return;
}
int main(int argc,char *argv[]){
n=read(),m=read();
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int x(read()),y(read());
addEdge(x,y);
addEdge(y,x);
}
for(int i=1;i<=n;i++)
if(dfn[i]==0){
s=i;
cutNode(i,i);
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(flag[i])
printf("%d\n",i);
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...