社区讨论

【求助】和std对拍无误然而零分

P3388【模板】割点(割顶)参与者 5已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mi6ldysw
此快照首次捕获于
2025/11/20 06:46
4 个月前
此快照最后确认于
2025/11/20 06:46
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 400000 + 100;
struct l {
    int to,next;
} line[maxn];
int first[maxn];
int llow[maxn];
int n,m,linecount;
int is_cut[maxn];
int dfn[maxn];
int ccount,nowgen;
int read(int a,int b) {
    linecount++;
    line[linecount].next = first[a];
    line[linecount].to = b;
    first[a] = linecount;
}
int dfs(int now,int dfnnow,int fa) {
    int x = 0;
    llow[now] = dfnnow;
    dfn[now] = dfnnow;
    for(int i=first[now];i;i=line[i].next) {
        int v = line[i].to;
        if(v == fa) continue;
        if(!dfn[v]) {
            if(now == nowgen) x++;
            dfs(v,dfnnow+1,now);
            llow[now] = min(llow[now],llow[v]);
        }
        else llow[now] = min(llow[now],dfn[v]);
    }
    if(now == fa) {
        if(x == 2) is_cut[++ccount] = now;
        return 0;
    }
    for(int i=first[now];i;i=line[i].next) {
        int v = line[i].to;
        if(v == fa) continue;
        if(llow[v] >= dfn[now]) {
            is_cut[++ccount] = now;
            break;
        }
    }
    return 0;
}
int get(int gen) {
    nowgen = gen;
    dfs(gen,1,gen);
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        read(x,y);
        read(y,x);
    }
    for(int i=1;i<=n;i++) {
        if(!dfn[i]) get(i);
    }
    sort(is_cut+1,is_cut+ccount+1);
    cout<<ccount<<endl;
    for(int i=1;i<=ccount;i++) printf("%d ",is_cut[i]);
}

回复

9 条回复,欢迎继续交流。

正在加载回复...