Cod sursa(job #1135396)

Utilizator SorinaSmeureanuSorina Smeureanu SorinaSmeureanu Data 7 martie 2014 20:01:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

int nr=0, niv1[100000], niv2[100000];
vector<int> a[100000], componente[100000];
stack < pair <int,int> > stiva;

void DFS(int vf, int tata, int niv)
{
    int i, vecin, x, y;
    niv1[vf]=niv;
    niv2[vf]=niv;
    for(i=0;i<a[vf].size();i++)
    {
        vecin=a[vf][i];
        if(tata==vecin)
            continue;
        if(niv1[vecin]==-1)
        {
            stiva.push(make_pair(vf, vecin));
            DFS(vecin, vf, niv+1);
            niv2[vf]=min(niv2[vf], niv2[vecin]);
            if(niv1[vf]<=niv2[vecin])
            {
                do
                {
                        x=stiva.top().first;
                        y=stiva.top().second;
                        stiva.pop();
                        componente[nr].push_back(y+1);
                } while(x!=vf && y!=vecin);
                componente[nr].push_back(x+1);
                nr++;
            }
        }
        else
            niv2[vf]=min(niv2[vf], niv1[vecin]);
   }
}

int main()
{
    int i, x, y, m, n, j;
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>x>>y;
        a[x-1].push_back(y-1);
        a[y-1].push_back(x-1);
    }
    for(i=0; i<n; i++)
        niv1[i]=-1;
    for(i=0;i<n;i++)
        DFS(i,0,0);
    g<<nr<<"\n";
    for(i=0;i<nr;i++)
    {
        for(j=0;j<componente[i].size();j++)
            g<<componente[i][j]<<" ";
        g<<"\n";
    }
}