只有输出顺序不同,为什么0pt? 不是任意顺序都行吗

P8436 【模板】边双连通分量

DreamTsinghua @ 2023-11-13 07:35:03


#include <bits/stdc++.h>

using namespace std ;

const int N = 4e6 + 10 ;

int n, m ;
int e[N], ne[N], h[N], idx ;
int dfs[N], low[N], id[N], dcc_cnt ;
bool st[N] ;
int din[N] ;
//vector <vector<int>> ans ;
vector <int> ans[N] ;

int ti ;
stack <int> s ;

void add(int a, int b) {
    e[idx] = b ;
    ne[idx] = h[a] ;
    h[a] = idx ++ ;
}

void tarjan(int u, int from) {
    dfs[u] = low[u] = ++ ti ;
    s.push(u) ;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i] ;
        if (!dfs[j]) {
            tarjan(j, i) ;
            low[u] = min(low[u], low[j]) ;
            if (dfs[u] < low[j])
                st[i] = st[i ^ 1] =  1 ;
        } else if (i != (from ^ 1))
            low[u] = min(low[u], dfs[j]) ;
    }

    if (dfs[u] == low[u]) {
        int y ;
        ++ dcc_cnt ;
        do {
            y = s.top() ;
            s.pop() ;
            id[y] = dcc_cnt ;
        } while (u != y) ;
    }
}

int main() {
    cin >> n >> m ;

    memset(h, -1, sizeof h) ;
    for (int i = 1;  i <= m ; i ++) {
        int a, b ;
        cin >> a >> b ;
        if (a == b)
            continue ;

        add(a, b) ;
        add(b, a) ;
    }

    for (int i = 1 ; i <= n ; i ++)
        if (dfs[i] == 0)
            tarjan(i, -1) ;

    cout << dcc_cnt << endl ;

    for (int i = 1 ; i <= n ; i ++) {
        ans[id[i]].push_back(i) ;
    }
    for (int i = 1 ; i <= dcc_cnt ; i ++) {
        cout << ans[i].size() << ' ' ;
        for (auto t : ans[i])
            cout << t << ' ' ;
        cout << endl ;
    }
    return 0 ;
}

样例1:
4 3
1 2
4 2
2 2

程序输出:
4
1 4
1 2
1 1
1 3
答案输出:
4
1 1
1 2
1 3
1 4

什么原因啊qwq
``

by lyxleo @ 2023-11-13 07:38:01

评测机炸了,UKE


by DreamTsinghua @ 2023-11-13 09:12:31

@lyxleo 蟹蟹


|