社区讨论

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

正在加载回复...