社区讨论

求助,悬关

灌水区参与者 6已保存回复 13

讨论操作

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

当前回复
13 条
当前快照
1 份
快照标识符
@m2a5fdk6
此快照首次捕获于
2024/10/15 15:55
去年
此快照最后确认于
2025/11/04 23:54
4 个月前
查看原帖
此代码MLE之处在哪(本地正常运行,LG上全MLE)
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,x,y,ans;
vector<int>a[100010];
int low[100010],dfn[100010],ge[100010];
int dfs(int now,int root){
    low[now]=dfn[now]=++cnt;
    int ch=0;
    for(int i=0;i<a[now].size();i++){
        int v=a[now][i];
        if(!dfn[v]){
            dfs(v,root);
            low[now]=min(low[now],low[v]);
            if(low[v]>=dfn[now]&&now!=root)ge[now]=1;
            if(now==root)ch++;
        }else low[now]=min(low[now],dfn[v]);
    }
    if(ch>=2&&root==now)ge[root]=1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])dfs(i,i);
    }
    for(int i=1;i<=n;i++){
        if(ge[i]==1)ans++;
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        if(ge[i]==1)cout<<i<<" ";
    }
    return 0;
}

回复

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

正在加载回复...