Cod sursa(job #1650714)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 11 martie 2016 20:02:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define nmax 100006
using namespace std;

int n,m1;
unsigned int niv[nmax],tata[nmax];
vector<int> m[nmax],cb;
vector < vector<int> > sol;
stack<int> s;

void get_sol(int nod,int dad)
{
    cb.clear();
    int crt;
    while(s.top()!=nod) { cb.push_back(s.top()); s.pop(); }
    s.pop();
    cb.push_back(nod); cb.push_back(dad);
    sol.push_back(cb);
}

void con(int nod,int dad)
{
    niv[nod]=niv[dad]+1; tata[nod]=niv[dad]+1;
    vector<int>::iterator it;
    for(it=m[nod].begin();it!=m[nod].end();it++)
        if(!niv[*it])
        {
            s.push(*it);
            con(*it,nod);
            tata[nod]=min(tata[nod],tata[*it]);
            if(tata[*it]>=niv[nod])
                get_sol(*it,nod);
        } else tata[nod]=min(tata[nod],niv[*it]);
}

int main()
{
    int n1,n2,i,j;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(;m1;m1--)
    {
        scanf("%d%d",&n1,&n2);
        m[n1].push_back(n2);
        m[n2].push_back(n1);
    }

    for(i=1;i<=n;i++)
        if(!niv[i])
        {
            s.push(i);
            con(i,0);
        }

    printf("%d\n",sol.size());
    for(i=0;i<sol.size();i++)
    {
        for(j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]); printf("\n");
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}