Cod sursa(job #2501048)

Utilizator gruhtenZinnenberg Gruhten gruhten Data 29 noiembrie 2019 00:19:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include<vector>
#include<deque>
using namespace std;
const int dim=100001;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,j,k=0, t[dim], nr, m,x,y;
unsigned  int nivel[dim], Low[dim];

vector<int> G[dim], a[dim];
deque<pair<int,int> >Q;

void dfs(int nod, int niv)
{
    Low[nod]=niv;
    nivel[nod]=niv;

    //int N=G[nod].size();
    for(int i=0; i<G[nod].size(); ++i)
    {
        int vecin=G[nod][i];

        if(Low[vecin]==0)
        {
            t[vecin]=nod;
            Q.push_back(make_pair(nod, vecin));

            dfs(vecin,niv+1);

            Low[nod]=min(Low[nod],Low[vecin]);

            if(Low[vecin]>=niv) //if(Low[vecin>=Low[nod])
            {
                k++;
                while(!Q.empty() and Q.back().first != nod)
                {
                    a[k].push_back(Q.back().second);
                    Q.pop_back();
                }

                Q.pop_back();
                a[k].push_back(vecin);
                a[k].push_back(nod);
            }
        }//end if(Low[vecin]==0)
        else
        {
            if(t[nod]!=vecin)
                    Low[nod]=min(Low[nod],nivel[vecin]);
        }
    }//end for(i=0; i<N; ++i)
}

int main()
{


    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

        dfs(1,1);
        g<<k<<'\n';
        for(int i=1;i<=k;i++)
        {
            int N=a[i].size();
            //g<<N<<' ';
            for(j=0;j<N;++j)
                g<<a[i][j]<<' ';

             g<<'\n';
        }


    return 0;
}