Cod sursa(job #2399139)

Utilizator AlexToveAlexandru Toader AlexTove Data 6 aprilie 2019 22:45:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100005

struct muchie
{
    int x, y;
}S[NMAX];

int T[NMAX], niv[NMAX], low[NMAX], N, nivel, sol, n;
vector<int>G[NMAX], B[NMAX];

void citire(), biconex(), DFS(int), componenta(int, int), afisare();

int main()
{
    citire();
    biconex();
    afisare();
    return 0;
}

void citire()
{
    ifstream fin("biconex.in");
    int m, i, x, y;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fin.close();
}

void componenta(int x, int y)
{
    int i, j;
    sol++;
    do
    {
        i=S[N].x, j=S[N].y, N--;
        B[sol].push_back(j);
    }while(i != x && j != y);
    B[sol].push_back(x);
}

void DFS(int nod)
{
    int fiu;
    vector<int>::iterator it, it2;

    nivel++;
    niv[nod] = low[nod] = nivel;

    for(it = G[nod].begin(), it2 = G[nod].end(); it != it2; it++)
    {
        fiu = *it;
        if(*it != T[nod])
        {
            if(!niv[fiu])
            {
                N++, S[n].x = nod, S[N].y = fiu;
                T[fiu] = nod;
                DFS(fiu);
                if(low[fiu] >= niv[nod])
                    componenta(nod, fiu);
                low[nod] = min(low[nod], low[fiu]);
            }
            else
                low[nod] = min(low[nod], niv[fiu]);
        }
    }
}

void biconex()
{
    for(int i=1; i<=n; i++)
        if(!niv[i])
            DFS(i);
}

void afisare()
{
    ofstream fout("biconex.out");
    vector<int>::iterator it, it2;
    fout<<sol<<'\n';
    for(int i=1; i<=sol; i++)
    {
        for(it=B[i].begin(), it2=B[i].end(); it!=it2; it++)
            fout<<*it<<" ";
        fout<<'\n';
    }
}