Cod sursa(job #1482999)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 8 septembrie 2015 14:48:18
Problema Componente biconexe Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <stack>
#include <vector>
#define Nmax 100010
#define mini(a,b) ((a)<(b)? (a):(b));
using namespace std;
int n,m1,niv[Nmax],minim[Nmax];
vector <int> m[Nmax],aux;
vector < vector<int> > sol;
stack<int> st;

void afisare(int nod, int tata)
{
    aux.clear();
    while(st.top()!=nod) {aux.push_back(st.top()); st.pop(); }
    st.pop();
    aux.push_back(nod); aux.push_back(tata);
    sol.push_back(aux);

}

void parc(int nod,int dad)
{
    niv[nod]=dad+1; minim[nod]=dad+1;
    for(vector<int>::iterator it=m[nod].begin();it!=m[nod].end();++it)
    {
        if(*it==dad) continue;
        if(!niv[*it])
        {
            st.push(*it);
            parc(*it,nod);
            minim[nod]=mini(minim[nod],minim[*it]);
            if(minim[*it]>=niv[nod])
            afisare(*it,nod);
        }
        else minim[nod]=mini(minim[nod],niv[*it]);
    }
    //for(i=1;i<=n;i++)
}

int main()
{
    int n1,n2,i;
    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])
        {
            st.push(i);
            parc(i,0);
            st.pop();
        }

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