Cod sursa(job #2410519)

Utilizator cicero23catalin viorel cicero23 Data 20 aprilie 2019 09:39:19
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb

#include <iostream>

#include <fstream>

#include <vector>

#include <stack>

#include <algorithm>

#define f first

#define s second

#define mp make_pair

#define N 100001

using namespace std;

ifstream f("biconex.in");

ofstream g("biconex.out");

vector <int> v[N];

stack <pair<int,int> > st;

vector <int> rez[N];

pair<int,int> aux;

int viz[N],t[N],niv[N],low[N],sol[N],r,nr,cont;

void DF(int x)

{

    int i;

    viz[x]=1;

    low[x]=niv[x];

    for(i=0; i<v[x].size(); i++)

    {

        if(v[x][i]!=t[x]&&niv[x]>niv[v[x][i]])

        {

            st.push(mp(x,v[x][i]));

            if(!viz[v[x][i]])

            {

                niv[v[x][i]]=niv[x]+1;

                t[v[x][i]]=x;

                DF(v[x][i]);

                low[x]=min(low[x],low[v[x][i]]);

                if(low[v[x][i]]>=niv[x])

                {

                    cont++;

                    do

                    {

                        aux=st.top();

                        rez[cont].push_back(aux.f);

                        rez[cont].push_back(aux.s);

                        st.pop();

                    }while((aux.f!=x||aux.s!=v[x][i])&&(aux.s!=x||aux.f!=v[x][i]));



                }

            }

            else if(v[x][i]!=t[x])

            {

                low[x]=min(low[x],niv[v[x][i]]);

            }

        }

    }

}

int main()

{

    int n,m,i,x,y,j;

    f>>n>>m;

    for(i=1;i<=m;i++)

    {

        f>>x>>y;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    viz[1]=1;

    niv[1]=1;

    DF(1);

    g<<cont<<'\n';

    for(i=1;i<=cont;i++)

    {

        sort(rez[i].begin(),rez[i].end());

    }

    for(i=1;i<=cont;i++)

    {

        g<<rez[i][0]<<" ";

        for(j=1;j<rez[i].size();j++)

        if(rez[i][j]!=rez[i][j-1])g<<rez[i][j]<<" ";

        g<<'\n';

    }

    return 0;

}