Cod sursa(job #1163187)

Utilizator sebinechitasebi nechita sebinechita Data 1 aprilie 2014 11:13:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define MAX 100100
#define pb push_back
#define mp make_pair

typedef vector <int> :: iterator iter;
vector <int> G[MAX];
vector< vector < int > > ans;

int ad[MAX], ad_fiu[MAX], dr, viz[MAX];
pair <int,  int> st[MAX];
void make_component(int x, int y)
{
    int nx, ny;
    vector <int> xy;
    do{
        nx=st[dr].first;
        ny=st[dr].second;
        dr--;
        xy.pb(ny);
    }while(nx!=x || ny!=y);
    xy.pb(nx);
    ans.pb(xy);
}

void df(int nod, int parinte, int adancime)
{

    viz[nod]=1;
    ad[nod]=adancime;
    ad_fiu[nod]=adancime;
    for(iter it=G[nod].begin();it!=G[nod].end();it++)
    {
        if(*it==parinte)
            continue;
        if(viz[*it])
        {
            ad_fiu[nod]=min(ad_fiu[nod], ad[*it]);
        }
        else
        {
            st[++dr]=mp(nod, *it);
            df(*it, nod, adancime+1);
            ad_fiu[nod]=min(ad_fiu[nod], ad_fiu[*it]);
            if(ad_fiu[*it]>=ad[nod])
                make_component(nod, *it);
        }
    }


}

int main()
{
    int n, m, x, y;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }

    df(1, 0, 1);
    fout<<ans.size()<<"\n";
    while(ans.size())
    {
        for(iter it=ans[ans.size()-1].begin();it!=ans[ans.size()-1].end();it++)
        {
            fout<<*it<<" ";
        }
        fout<<"\n";
        ans.pop_back();
    }

}