求助,为啥我用vector建图50pts

P8436 【模板】边双连通分量

Archy_ @ 2024-07-10 11:05:45

看了一些,我输出的边双连通分量个数大于正解,是不是哪里的判定条件少了,我看了好久,求助!!!

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#define N 500010
#define M 2000010

using namespace std;

int n, m, low[N], dfn[N], dfncnt, bcccnt;
bool vis[N];
vector <int> g[N],ans[N];
map <pair<int,int>,bool> mp;

inline int rd() {
    int w = 1, x = 0;
    char c = getchar();
    while(c < 48 || c > 57) {
        if(c == 45) w *= -1;
        c = getchar();
    }
    while(c >= 48 && c<= 57) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * w;
}

void tarjan(int u, int fa){
    dfn[u] = low[u] = ++dfncnt;
    for(int &v : g[u]){
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]){
                mp[pair<int, int>(u, v)] = 1;
                mp[pair<int, int>(v, u)] = 1;
            }
        }
        else if(v != fa)low[u] = min(low[u], dfn[v]);
    }
}

void dfs(int u,int id){
    vis[u] = 1;
    ans[bcccnt].push_back(u);
    for(auto &v : g[u]){
        if(mp[pair<int, int>(u, v)] || vis[v]) continue;
        if(!vis[v]) dfs(v, id);
    }
}

int main() {

    n = rd(), m = rd();
    for(int i = 1;i <= m;i ++) {
        int u = rd(), v = rd();
        g[u].push_back(v);
        g[v].push_back(u);
    }

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

    for(int i = 1;i <= n;i ++)
            if(!vis[i])
                dfs(i,++bcccnt);

    printf("%d\n",bcccnt);
    for(int i = 1;i <= bcccnt;i ++) {
        printf("%d ",ans[i].size());
        for(int &j : ans[i]) 
            printf("%d ",j);
        printf("\n");
    }

    return 0;
}

by Archy_ @ 2024-07-10 11:06:43

mp是边与bool的映射,判断bridge的


by hao_zi6366 @ 2024-08-01 20:39:59

有重边的可能性,当一条边被多次输入时,这条边不可能是桥。


|