Cod sursa(job #1347723)

Utilizator 0051David Sera 0051 Data 19 februarie 2015 09:49:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define MAX 100010

typedef vector < int > ::iterator iter;
vector < int > g[MAX];
vector < vector < int > > f;
int h[MAX],d[MAX],viz[MAX];
pair < int, int > st[MAX];
int lg,dr;

void cb(int x, int y)
{
    vector < int > aux;
    while(st[dr] != make_pair(x,y))
    {
        aux.push_back(st[dr].second);
        dr--;
    }
    aux.push_back(y);
    aux.push_back(x);
    dr--;
    f.push_back(aux);
}

void df(int nod, int dad)
{
    lg++;
    h[nod]=d[nod]=lg;
    viz[nod]=1;
    for(iter it=g[nod].begin();it!=g[nod].end();it++)
    {
        if(*it==dad)
            continue;
        if(viz[*it])
        {
            h[nod]=min(h[nod], d[*it]);
        }
        else
        {
            st[++dr]=make_pair(nod,*it);
            df(*it,nod);
            h[nod]=min(h[nod], h[*it]);
            if(h[*it] >= d[nod])
            {
                cb(nod, *it);
            }
        }
    }
    lg--;
}

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    df(1,0);
    fout<<f.size();
    fout<<"\n";
    for(int i=0;i<f.size();i++)
    {
        for(int j=0;j<f[i].size();j++)
            fout<<f[i][j]<<" ";
        fout<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}