Cod sursa(job #2475871)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 17 octombrie 2019 18:24:09
Problema Componente biconexe Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=1e5+4;

int n,m,cnt;
int dfn[NMAX],low[NMAX];
stack <int> stk;
vector <int> g[NMAX];
vector <int> cb[NMAX];

void dfs(int node, int father){
    dfn[node]=dfn[father]+1;
    low[node]=dfn[node];

    stk.push(node);

    for(auto it:g[node]){
        if(dfn[it] && it!=father)
            low[node]=min(low[node], low[it]);
        else if(!dfn[it]){
            int id=dfn[node];
            dfs(it, node);
            low[node]=min(low[node], low[it]);
            if(low[it]>=id){
                while(!stk.empty() && low[stk.top()]>=id){

                    cb[cnt].push_back(stk.top());
                    stk.pop();
                }
                if(cb[cnt][cb[cnt].size()-1] !=node)
                    cb[cnt].push_back(node);
                else
                    stk.push(node);
                ++cnt;
            }
        }
    }
}

int main(){
    int x,y;
    fin>>n>>m;
    for(int i=0;i<m;++i){
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    fout<<cnt<<'\n';
    for(int i=0;i<cnt;++i){
        for(auto it:cb[i])
            fout<<it<<' ';
        fout<<'\n';
    }
    return 0;
}