76分求助,4、6、11WA,代码使用邻接表和dfs来实现
查看原帖
76分求助,4、6、11WA,代码使用邻接表和dfs来实现
485189
wdstql2333楼主2021/4/16 00:52
#include<iostream>
using namespace std;
int first[200001]{0},next_[200001]{0},result[20001]{0},pre[20001],low[20001],u[200001]{0}, v[200001]{0};;
int root{0},index{0},n,m,sum{0};
int min_(int a,int b){
    return a > b ? b : a;
}
void dfs(int cur){
    int child=0,i;
    index++;
    pre[cur] = index;
    low[cur] = index;
    i = first[cur];
    while(i!=0){
        if(pre[v[i]]==0){
            child++;
            dfs(v[i]);
            low[cur] = min_(low[cur], low[v[i]]);
            if(cur!=root){
                if(pre[cur]==low[v[i]]){
                    result[cur] = 1;
                    sum++;
                }
            }
            else if(child>=2){
                result[cur] = 1;
                sum++;
            }
        }
        else
            low[cur] = min_(low[cur], pre[v[i]]);
        i = next_[i];
    }
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= m;i++){
        cin >> u[i] >> v[i];
    }
    for (int i = m + 1; i <= 2 * m;i++){
        u[i] = v[i - m];
        v[i] = u[i - m];
    }
    for (int i = 1; i <=2*m;i++){
        next_[i] = first[u[i]];
        first[u[i]] = i; 
    }
    root = u[1];
    dfs(root);
    cout << sum << endl;
    for (int i = 1; i <= n;i++){
        if(result[i]!=0){
            cout << i << " ";
        }
    }
    return 0;
}


2021/4/16 00:52
加载中...