Cod sursa(job #1666370)

Utilizator robertkarolRobert Szarvas robertkarol Data 27 martie 2016 23:26:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> v[100001], cbc[100001];
stack<pair<int,int>> s;
int n,m,i,x,y,niv[100001],low[100001],k;
void biconex(int nod, int fiu)
{
    k++;
    do
    {
        x=s.top().first;
        y=s.top().second;
        s.pop();
        cbc[k].push_back(y);
    }
    while(x!=nod && y!=fiu);
    cbc[k].push_back(nod);
}
void dfbc(int nod, int tata, int nivel)
{
    int i,fiu;
    niv[nod]=low[nod]=nivel;
    for(i=0;i<v[nod].size();i++)
    {
        fiu=v[nod][i];
        if(fiu!=tata)
        {
            if(!niv[fiu])
            {
                s.push(make_pair(nod,fiu));
                dfbc(fiu,nod,nivel+1);
                low[nod]=min(low[nod],low[fiu]);
                if(low[fiu]>=niv[nod]) biconex(nod,fiu);
            }
            else low[nod]=min(low[nod],low[fiu]);
        }

    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!niv[i]) dfbc(i,0,1);
    fout<<k<<"\n";
    vector<int>::iterator j;
    for(i=1;i<=k;i++)
        {
            for(j=cbc[i].end()-1;j>=cbc[i].begin();j--)
                fout<<*j<<" ";
            fout<<"\n";
        }
    return 0;
}