Cod sursa(job #1964552)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 13 aprilie 2017 14:59:15
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n,m;

vector<int> L[100005];

int ncomp;
int LOW[100005],DFN[100005];
vector<int> SOL[100005];
stack<int> S;

void read(){
    in>>n>>m;
    for(int i=1,x,y;i<=m;i++){
        in>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
}
void dfs(int nod){
    S.push(nod);
    for(auto x : L[nod]){
        if(!LOW[x]){
            int c=S.size();
            LOW[x]=DFN[x]=DFN[nod]+1;
            dfs(x);
            LOW[nod]=min(LOW[nod],LOW[x]);
            if(LOW[x]>=DFN[nod]){ //! => nod= punct de articulatie
                ncomp++;
                while(S.size()>c){
                    SOL[ncomp].push_back(S.top());
                    S.pop();
                }
                SOL[ncomp].push_back(nod);
            }
        }
        else LOW[nod]=min(LOW[nod],DFN[x]);
    }
}
void solve(){
    LOW[1]=DFN[1]=1;
    dfs(1);
    out<<ncomp<<"\n";
    for(int i=1;i<=ncomp;i++){
        for(auto x : SOL[i]){
            out<<x<<" ";
        }
        out<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}