Cod sursa(job #2096491)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 29 decembrie 2017 12:31:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N = 100002;
int dep[N], lowest[N], st[N][2], stSize, nrBiComp;
bool viz[N];
vector <int> v[N], comp[N];
void newBiComp(int ns, int nbr){
    nrBiComp++;
    while(!(st[stSize][0] == ns && st[stSize][1] == nbr))
        comp[nrBiComp].push_back(st[stSize--][1]);
    stSize--;
    comp[nrBiComp].push_back(ns);
    comp[nrBiComp].push_back(nbr);
}
void DFS(int ns){
    int sz = v[ns].size(), nbr;
    viz[ns] = true;
    lowest[ns] = dep[ns];
    for(int i=0;i<sz;i++){
        nbr = v[ns][i];
        if(viz[nbr] == false){
            dep[nbr] = dep[ns] + 1;
            st[++stSize][0] = ns;
            st[stSize][1] = nbr;
            DFS(nbr);
            if(lowest[nbr] >= dep[ns])
                newBiComp(ns,nbr);
            if(lowest[ns] > lowest[nbr])
                lowest[ns] = lowest[nbr];
        }
        else if(lowest[ns] > dep[nbr])
            lowest[ns] = dep[nbr];
    }
}
int main()
{
    int n,m,x,y,sz;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    in.close();
    DFS(1);
    out<<nrBiComp<<"\n";
    for(int i=1;i<=nrBiComp;i++){
        sz = comp[i].size();
        for(int j=0;j<sz;j++)
            out<<comp[i][j]<<" ";
        out<<"\n";
    }
    out.close();
    return 0;
}