Cod sursa(job #2217232)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 29 iunie 2018 17:38:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

#define pii pair<int, int> 
#define ll long long
#define pll pair<ll, ll> 
#define NMax 100010
#define oo 1000000000
#define MOD 998244353

using namespace std;

ofstream fout("biconex.out");
ifstream fin("biconex.in");

stack<int> S;
vector<int> ans[NMax];
int nrC;
vector<int> G[NMax];
int n, m, x, y;
int l[NMax];
int d[NMax];

void dfs(int node, int depth, int prev){
    d[node] = depth;
    l[node] = depth;
    S.push(node);
    for(auto next : G[node]){
        if(!d[next]){
            dfs(next, depth + 1, node);
            if(l[next] < d[node]) l[node] = min(l[node], l[next]);
            else{
                nrC++;

                int v;
                do{
                    v = S.top();
                    S.pop();
                    ans[nrC].push_back(v);
                }while(v != next);

                ans[nrC].push_back(node);
            }
        }

        else{
            if(next != prev) l[node] = min(l[node], d[next]);
        }
    }
}

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

    for(int i = 1; i <= m; i++){
        fin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(1, 1, 0);

    fout << nrC << '\n';

    for(int i = 1; i <= nrC; i++){
        for(int j = 0; j < ans[i].size(); j++){
            fout << ans[i][j] << ' ';
        }

        fout << '\n';
    }

    fin >> n;

    return 0;
}