P8436 【模板】边双连通分量

Question

为什么过不了洛谷的P8436 【模板】边双连通分量
只有50分

```c++
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define 
#define ll long long


const int N=5e5+5;

const int M=2e6+5;

int dfn[N],low[N];
int tot;
int n,m;
vector<int>q[M];
int in[N];
stack<int>e;
int col;

queue<int>p[N];

void tarjan(int x,int y){
    
    dfn[x]=++tot;
    low[x]=tot;
    in[x]=1;
    e.push(x);
    
    for(auto it:q[x]){
        if(!dfn[it]){
            tarjan(it,x);
            low[x]=min(low[x],low[it]);
            
        }
        else if(in[it]){
            if(it!=y){
                low[x]=min(low[x],dfn[it]);
            }
        }
    }

    if(low[x]==dfn[x]){
        col++;
        while(e.top()!=x){
            p[col].push(e.top());
            in[e.top()]=0;
            e.pop();
        }
        //in[x]=0;
        p[col].push(x);
        e.pop();
    }
    
    
}

void solve(){
    cin>>n>>m;

    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        q[a].push_back(b);
        q[b].push_back(a);
    }
    
    
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,0);
    }
    
    
    cout<<col<<endl;

    for(int i=1;i<=col;i++){
        cout<<p[i].size()<<' ';
        while(!p[i].empty()){
            cout<<p[i].front()<<' ';
            p[i].pop();
        }
        cout<<endl;
    }
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
}

```

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

问题分析

用户在洛谷提交的P8436【模板】边双连通分量问题只得到了50分，说明代码存在一些问题。我们需要仔细分析代码，找出可能导致错误的原因。

关键点分析

1. Tarjan算法实现：用户使用了Tarjan算法来寻找边双连通分量。Tarjan算法的关键在于正确更新dfn和low数组，并且在回溯时正确处理栈中的节点。
2. 栈的使用：在Tarjan算法中，栈用于存储当前搜索路径上的节点。需要确保在弹出节点时正确更新相关状态。
3. 输出格式：输出的边双连通分量的数量和每个分量的节点列表需要符合题目要求。

代码审查

1. 栈的弹出操作：在Tarjan算法中，当low[x] == dfn[x]时，需要弹出栈中的节点直到遇到当前节点x。当前代码在弹出节点时没有正确更新in数组。
2. 输出格式：需要确保输出的边双连通分量的数量和每个分量的节点列表格式正确。

解决方案

1. 修正栈的弹出操作：在弹出节点时，确保正确更新in数组。
2. 确保输出格式正确：检查输出的边双连通分量的数量和每个分量的节点列表格式是否符合题目要求。

修改后的代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

const int N = 5e5 + 5;
const int M = 2e6 + 5;

int dfn[N], low[N];
int tot;
int n, m;
vector<int> q[M];
int in[N];
stack<int> e;
int col;

queue<int> p[N];

void tarjan(int x, int y) {
    dfn[x] = ++tot;
    low[x] = tot;
    in[x] = 1;
    e.push(x);

    for (auto it : q[x]) {
        if (!dfn[it]) {
            tarjan(it, x);
            low[x] = min(low[x], low[it]);
        } else if (in[it]) {
            if (it != y) {
                low[x] = min(low[x], dfn[it]);
            }
        }
    }

    if (low[x] == dfn[x]) {
        col++;
        while (true) {
            int top = e.top();
            e.pop();
            in[top] = 0;
            p[col].push(top);
            if (top == x) break;
        }
    }
}

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        q[a].push_back(b);
        q[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, 0);
    }

    cout << col << endl;

    for (int i = 1; i <= col; i++) {
        cout << p[i].size() << ' ';
        while (!p[i].empty()) {
            cout << p[i].front() << ' ';
            p[i].pop();
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

修改说明

1. 修正栈的弹出操作：在tarjan函数中，当low[x] == dfn[x]时，使用一个循环来弹出栈中的节点，并更新in数组。
2. 确保输出格式正确：输出的边双连通分量的数量和每个分量的节点列表格式符合题目要求。

通过上述修改，代码应该能够正确处理边双连通分量问题，并通过洛谷的P8436题目。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑