Cod sursa(job #1970535)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 19 aprilie 2017 13:50:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#define NMax 100005
#define MMax 200005
using namespace std;

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

vector<int> G[NMax], sol[NMax];
struct date {int x, y;} st[MMax];
int i, j, varf, N, M, nrsol, a, b;
int ap[NMax], niv[NMax], low[NMax];

void DFS (int nod, int nivel, int tata)
{
    ap[nod]=1; niv[nod]=nivel; low[nod]=nivel;

    for(int i=0; i<G[nod].size(); i++)
    {
        int fiu=G[nod][i];
        if(tata!=fiu)
        {
            if(!ap[fiu])
            {
                ++varf;
                st[varf].x=nod; st[varf].y=fiu;

                DFS(fiu, nivel+1, nod);

                if(low[fiu]>=nivel)
                {
                    ++nrsol;
                    sol[nrsol].pb(nod);

                    while(st[varf].x!=nod)
                    {
                        sol[nrsol].pb(st[varf].y);
                        varf--;
                    }
                    sol[nrsol].pb(fiu);
                    varf--;
                }
                low[nod]=min(low[nod], low[fiu]);
            }
            else low[nod]=min(low[nod], niv[fiu]);
        }
    }
}

int main()
{
    f>>N>>M;
    for(i=1; i<=M; i++)
    {
        f>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }

    DFS(1,1,0);

    g<<nrsol<<'\n';
    for(i=1; i<=nrsol; i++)
    {
        for(j=0; j<sol[i].size(); j++)
            g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}