QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1267#792613#999. 边双连通分量RDFZchenyyoyzrFailed.2024-11-29 12:00:342024-11-29 12:00:36

Details

Extra Test:

Accepted
time: 1ms
memory: 5652kb

input:

2 3
0 0
0 1
1 1

output:

2
1 1 
1 0 

result:

ok OK

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792613#999. 边双连通分量oyzrAC ✓46ms20764kbC++231.9kb2024-11-29 11:58:502024-11-29 11:58:50

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXM = 2e5 + 5;
int read(){
    int res = 0, flag = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            flag = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        res = (res << 1) + (res << 3) + (c ^ 48);
    return res * flag;
}
class Graph{
private:
    const static int MAXNODE = MAXN, MAXEDGE = MAXM * 2;
    struct Edge{
        int v, next;    
    };
    int tot = 1;
public:
    Edge t[MAXEDGE];
    int h[MAXNODE];
    void addEdge(int u, int v){
        ++tot;
        t[tot].v = v;
        t[tot].next = h[u];
        h[u] = tot;
    }
}G;
int dfn[MAXN], low[MAXN], cnt = 0;
int eccId[MAXN], eccCnt = 0;
vector <int> ecc[MAXN];
stack <int> s;
void tarjan(int u, int from){
    low[u] = dfn[u] = ++cnt;
    s.push(u);
    for (int i = G.h[u]; i; i = G.t[i].next){
        if (i == (from ^ 1))
            continue;
        int v = G.t[i].v;
        if (!dfn[v]){
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        }else
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]){
        ++eccCnt;
        int v;
        do {
            v = s.top();
            s.pop();
            eccId[v] = eccCnt;
            ecc[eccCnt].push_back(v); 
        }while (v != u);
    }
} 
int main(){
    int n = read(), m = read();
    for (int i = 1; i <= m; i++){
        int u = read(), v = read();
        u++, v++;
        G.addEdge(u, v);
        G.addEdge(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!eccId[i])
            tarjan(i, 0);
    cout << eccCnt << '\n';
    for (int i = 1; i <= eccCnt; i++){
        cout << ecc[i].size() << ' ';
        for (auto x: ecc[i])
            cout << x - 1 << ' ';
        cout << '\n';
    }
    return 0;
}