Cod sursa(job #1863832)

Utilizator DobosDobos Paul Dobos Data 31 ianuarie 2017 11:25:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

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

int low[NMAX],level[NMAX];
stack < int > S;
vector < int > G[NMAX];
vector < vector < int > > V;


void Addcomponent(int x,int y){
    vector < int > aux;
    int a;
    aux.push_back(x);
    do{
        a = S.top();
        S.pop();
        aux.push_back(a);

    }while(y != a);
    sort(aux.begin(),aux.end());
    V.push_back(aux);
}


void DFS(int nod,int lvl){
    low[nod] = level[nod] = lvl;
    S.push(nod);
    for(auto const &i : G[nod]){
        if(low[i] == 0){
            DFS(i,lvl + 1);
            low[nod] = min(low[nod],low[i]);
            if(low[i] >= level[nod])
                Addcomponent(nod,i);
        } else {
            low[nod] = min(low[nod],level[i]);
        }
    }



}


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m,x,y;

    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);
    fout << V.size() << "\n";
    for(auto const &i : V){
        for(auto const &j : i)
            fout << j << " ";
        fout << "\n";
        }
    return 0;
}