Cod sursa(job #781867)

Utilizator stefanzzzStefan Popa stefanzzz Data 25 august 2012 12:33:43
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

struct muchie{
    int nod1,nod2;};

int n,m,x,y,cnt,nrcbc,dfn[MAXN],low[MAXN],nrfii;
vector<int> G[MAXN],cbc[MAXN];
vector<muchie> stiva;
muchie aux;

void DFS(int p);

int main()
{
    int i,j;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);}
    DFS(1);
    if(nrfii>1){
        while(nrfii){
            nrfii--;
            nrcbc++;
            do{
                aux=stiva.back();
                stiva.pop_back();
                cbc[nrcbc].push_back(aux.nod2);}
            while(aux.nod1!=1);
            cbc[nrcbc].push_back(1);}}
    g<<nrcbc<<'\n';
    for(i=1;i<=nrcbc;i++){
        for(j=0;j<cbc[i].size();j++)
            g<<cbc[i][j]<<' ';
        g<<'\n';}
    f.close();
    g.close();
    return 0;
}

void DFS(int p){
    int i;
    dfn[p]=(++cnt);
    low[p]=cnt;
    for(i=0;i<G[p].size();i++){
        if(!dfn[G[p][i]]){
            aux.nod1=p;
            aux.nod2=G[p][i];
            stiva.push_back(aux);
            DFS(G[p][i]);
            if(low[G[p][i]]<low[p])
                low[p]=low[G[p][i]];
            if(p==1){
                nrfii++;
                continue;}
            if(low[G[p][i]]>=dfn[p]){
                ++nrcbc;
                do{
                    aux=stiva.back();
                    stiva.pop_back();
                    cbc[nrcbc].push_back(aux.nod2);}
                while(aux.nod1!=p||aux.nod2!=G[p][i]);
                cbc[nrcbc].push_back(p);}}
        else{
            if(dfn[G[p][i]]<low[p])
                low[p]=dfn[G[p][i]];}}}