Cod sursa(job #2410505)

Utilizator cicero23catalin viorel cicero23 Data 20 aprilie 2019 09:26:30
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[Nmax];
vector <int > ans[Nmax];
stack <pair<int,int> > st;
int viz[Nmax],low[Nmax],niv[Nmax],t[Nmax];
int cont;
void df(int x)
{
    viz[x]=1;
    low[x]=niv[x];
    for(int i=0;i<v[x].size();i++)
    {
        if(v[x][i]!=t[x]&&niv[x]>niv[v[x][i]])
        {
            st.push({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++;
                    pair<int,int>  aux;
                    do
                    {
                        aux=st.top();
                        ans[cont].push_back(aux.first);
                        ans[cont].push_back(aux.second);
                        st.pop();

                    }while((aux.first!=x||aux.second!=v[x][i])&&(aux.second!=x||aux.first!=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(ans[i].begin(),ans[i].end());
    }
    for(i=1;i<=cont;i++)
    {
        g<<ans[i][0]<<' ';
        for(j=1;j<ans[i].size();j++)
        if(ans[i][j]!=ans[i][j-1]) g<< ans[i][j]<<' ';
        g<<'\n';

    }
    return 0;
}