Cod sursa(job #1833106)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 21 decembrie 2016 17:24:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int n, m;
vector<int> vecini[100005];
int viz[100005];
int nivel[100005];
int sus[100005];
stack<int> S;
int nrComponente = 0;
vector<vector<int> > sol;

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2;

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &tmp1, &tmp2);
        tmp1--;
        tmp2--;
        vecini[tmp1].push_back(tmp2);
        vecini[tmp2].push_back(tmp1);
    }
}

void eliminare(int nod, int tata)
{
    vector<int> tmp;

    tmp.push_back(tata);

    while(S.top() != nod)
    {
        tmp.push_back(S.top());
        S.pop();
    }
    tmp.push_back(nod);
    S.pop();
    sol.push_back(tmp);
}

void dfs(int x, int tata)
{
    viz[x] = true;
    nivel[x] = nivel[tata] + 1;
    sus[x] = nivel[x];

    for(int i = 0; i < vecini[x].size(); i++)
    {
        if(vecini[x][i] == tata)
        {
            continue;
        }
        if(viz[vecini[x][i]] == false)
        {
            S.push(vecini[x][i]);

            dfs(vecini[x][i], x);

            sus[x] = min(sus[x], sus[vecini[x][i]]);

            if(nivel[x] <= sus[vecini[x][i]])
            {
                nrComponente++;
                eliminare(vecini[x][i], x);
            }
        }
        else
        {
            sus[x] = min(sus[x], nivel[vecini[x][i]]);
        }
    }
}

void afisare()
{
    printf("%d\n", nrComponente);

    for(int i = 0; i < sol.size(); i++)
    {
        for(int j = 0; j < sol[i].size(); j++)
        {
            printf("%d ", sol[i][j] + 1);
        }
        printf("\n");
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    citire();
    S.push(0);
    dfs(0, -1);
    afisare();

    return 0;
}