社区讨论
有点奇怪。。求大佬看看
P3388【模板】割点(割顶)参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6tp4va
- 此快照首次捕获于
- 2025/11/20 10:39 4 个月前
- 此快照最后确认于
- 2025/11/20 10:39 4 个月前
AC代码:
CPP#include<cstdio>
using namespace std;
const int maxn=(1e5)+5,maxE=(2e5)+5;
int n,m,ans,id[maxn],tot,son[maxE],nxt[maxE],lnk[maxn],T,T_in[maxn],low[maxn];bool vis[maxn];
char gt(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
int ret=0;char ch=gt();
while(ch<'0'||ch>'9') ch=gt();
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=gt();
return ret;
}
void write(int x){if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
void add_e(int x,int y){son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot;}
void Tarjan(int x,int fa){
low[x]=T_in[x]=++T;int cnt=0;
for(int j=lnk[x];j;j=nxt[j]){
if(!T_in[son[j]]){
Tarjan(son[j],x),cnt++;
if(low[son[j]]<low[x]) low[x]=low[son[j]];
if(low[son[j]]>=T_in[x]&&fa) vis[x]=1;
}else if(T_in[son[j]]<low[x]&&son[j]!=fa) low[x]=T_in[son[j]];
}
if(!fa&&cnt>1) vis[x]=1;
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
add_e(x,y),add_e(y,x);
}
for(int i=1;i<=n;i++) if(!T_in[i]) Tarjan(i,0);
for(int i=1;i<=n;i++) if(vis[i]) id[++ans]=i;
printf("%d\n",ans);
for(int i=1;i<ans;i++) write(id[i]),putchar(' ');if(ans) write(id[ans]),putchar('\n');
return 0;
}
0分代码:
CPP#include<cstdio>
using namespace std;
const int maxn=(1e5)+5,maxE=(2e5)+5;
int n,m,ans,id[maxn],tot,son[maxE],nxt[maxE],lnk[maxn],T,T_in[maxn],low[maxn];bool vis[maxn];
char gt(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
int ret=0;char ch=gt();
while(ch<'0'||ch>'9') ch=gt();
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=gt();
return ret;
}
void write(int x){if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
void add_e(int x,int y){son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot;}
void Tarjan(int x,int fa){
low[x]=T_in[x]=++T;int cnt=0;
for(int j=lnk[x];j&&son[j]!=fa;j=nxt[j]){
if(!T_in[son[j]]){
Tarjan(son[j],fa),cnt++;
if(low[son[j]]<low[x]) low[x]=low[son[j]];
if(low[son[j]]>=T_in[x]&&fa) vis[x]=1;
}else if(T_in[son[j]]<low[x]) low[x]=T_in[son[j]];
}
if(!fa&&cnt>1) vis[x]=1;
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
add_e(x,y),add_e(y,x);
}
for(int i=1;i<=n;i++) if(!T_in[i]) Tarjan(i,0);
for(int i=1;i<=n;i++) if(vis[i]) id[++ans]=i;
printf("%d\n",ans);
for(int i=1;i<ans;i++) write(id[i]),putchar(' ');if(ans) write(id[ans]),putchar('\n');
return 0;
}
(主要就Tarjan那块关于son[j]==fa的问题)
回复
共 0 条回复,欢迎继续交流。
正在加载回复...