社区讨论

有点奇怪。。求大佬看看

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 条回复,欢迎继续交流。

正在加载回复...