Cod sursa(job #2398339)

Utilizator DimaTCDima Trubca DimaTC Data 5 aprilie 2019 12:58:19
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include<bits/stdc++.h>
#define N 100030

using namespace std;

int n,m,t,k;
int disc[N], low[N];
vector<int>V[N], CB[N];
stack<int>S;

void DFS(int x, int pr) {
    disc[x]=low[x]=++t;
    S.push(x);
    for (auto it:V[x]) {
        if (it==pr) continue;
        if (!disc[it]) {
            DFS(it,x);
            if (low[it]>=disc[x]) {
                ++k;
                while (S.top()!=x) {
                    CB[k].push_back(S.top());
                    S.pop();
                }
                CB[k].push_back(x);
            }
            low[x]=min(low[it],low[x]);
        } else {
            low[x]=min(low[x], disc[it]);
        }
    }
}

int main() {
    ifstream cin("biconex.in");ofstream cout("biconex.out");
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y; cin>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    for (int i=1; i<=n; ++i)
        if (!disc[i]) DFS(i,-1);
    cout<<k<<'\n';
    for (int i=1; i<=k; ++i) {
        for (auto it:CB[i]) cout<<it<<" "; cout<<'\n';
    }
    return 0;
}