社区讨论

悬关:蒟蒻求助,测试案例出现问题

P8435【模板】点双连通分量参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lz9tpf5x
此快照首次捕获于
2024/07/31 20:28
2 年前
此快照最后确认于
2024/07/31 21:59
2 年前
查看原帖

代码:

CPP
#include<bits/stdc++.h>
#define N 500005
using namespace std;
vector<int> b[N];
int dfn[N],low[N],cnt=1;
stack<int> s;
int cntp=0;
set<int> p[N];
void tarjan(int x,int f){
    s.push(x);
    if(!dfn[x])
        dfn[x]=low[x]=cnt++;
    for(int i=0;i<b[x].size();i++){
        int y=b[x][i];
        if(y==f)
            continue;
        if(dfn[y])
            low[x]=min(low[x],dfn[y]);
        else{
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
        }
        if(dfn[x]==low[x]){
            cntp++;
            int cur;
            do{
                if(!s.size())
                    break;
                cur=s.top();
                s.pop();
                p[cntp].insert(cur);
            }
            while(cur!=x);
        }
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        b[u].push_back(v);
        b[v].push_back(u);
    }
    tarjan(1,-1);
    printf("%d\n",cntp);
    for(int i=1;i<=cntp;i++){
        printf("%d ",p[i].size());
        for(auto j:p[i])
            printf("%d ",j);
        printf("\n");
    }
}

主要问题:

CPP
1. 找不出孤立点
2. 有多余0输出
3. 重复点不会被输出
4. 由于蒟蒻很弱,更多问题待大佬帮忙发现

悬赏:

只要帮我解决问题,我就会关注TA
蒟蒻一定说到做到

求求了,帮帮蒟蒻吧。

回复

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

正在加载回复...