Cod sursa(job #1915071)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 8 martie 2017 19:33:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

const int Nmax = 100005;
const int Mmax = 200005;

vector < int > G[Mmax];
stack < pair <int, int > > st;

int N,M;
int nivel[Nmax], sus[Nmax];

void Read()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d%d", &N, &M);

    for(int i=1; i<=M; ++i)
    {
        int x,y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

int nr=0;

bitset <Nmax> viz;

vector < int > rez[Nmax];

void Transcript(int el)
{
    nr++;

    while(st.top().second!=el)
    {
      rez[nr].push_back(st.top().second);
      st.pop();
    }

    rez[nr].push_back(st.top().second);
    rez[nr].push_back(st.top().first);
    st.pop();

}

void dfs(int x, int dad)
{
    viz[x]=1;

    nivel[x]=nivel[dad]+1;
    sus[x]=nivel[x];

    vector <int>::iterator it;

    for(it=G[x].begin(); it!=G[x].end(); ++it)
    {
        if(*it==dad)
            continue;
        else if(!viz[*it])
        {
            st.push(make_pair(x,*it));
            dfs(*it,x);
            sus[x]=min(sus[*it], sus[x]);
            if(sus[*it]>=nivel[x])
                Transcript(*it);
        }
        else
            sus[x]=min(nivel[*it], sus[x]);
    }
}
int afi[Mmax];

void Print()
{
    cout<<nr<<"\n";
    for(int i=1; i<=nr; ++i)
    {int ind=0;
        for(vector <int>::iterator it=rez[i].begin(); it!=rez[i].end(); ++it)
            afi[++ind]=*it;


        for(int ind1=ind; ind1>=1; ind1--)
            cout<<afi[ind1]<<" ";
        cout<<"\n";
    }
}

int main()
{
    Read();

    for(int i=1; i<=N; ++i)
        if(!viz[i])
            dfs(i,0);

    Print();

  return 0;
}