Cod sursa(job #934729)

Utilizator vladm97Matei Vlad vladm97 Data 31 martie 2013 11:36:47
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<stack>
#include<iostream>
#include<vector>
#define dim 110000
#define lmare 250000
using namespace std;

vector<int>v[dim];
bool parcurs[dim];
int niv[dim],t[dim],nr,l[dim];
int c[lmare],k;
stack<int>s;

void df(int a)
{
    int i;
    s.push(a);
    parcurs[a]=true;
    l[a]=niv[a];
    for(i=0;i<v[a].size();i++)
        if(parcurs[v[a][i]]==0)
        {
        niv[v[a][i]]=niv[a]+1;
        t[v[a][i]]=a;
        df(v[a][i]);
        if(l[a]>l[v[a][i]])l[a]=l[v[a][i]];
        if(l[v[a][i]]>=niv[a])
        {
            nr++;
            while(s.top()!=a)
            {
               c[++k]=s.top();
               s.pop();
            }
            c[++k]=s.top();
            c[++k]=-1;
        }
        }
        else if(v[a][i]!=t[a] && l[a]>niv[v[a][i]])l[a]=niv[v[a][i]];

}
int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    int m,n,i,a,b;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=n;i>=1;i--)
    {
        if(parcurs[i]==0)
        {
            niv[i]=1;
            df(i);
        }
    }
    g<<nr<<"\n";
    for(i=1;i<=k;i++)
        if(c[i]==-1)g<<"\n";
        else g<<c[i]<<" ";
}