Cod sursa(job #1122204)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 25 februarie 2014 16:57:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

#define Nmax 100005

using namespace std;

int N, M, Nrc, Low[Nmax], Nivel[Nmax];
vector <int> G[Nmax], Sol[Nmax];
stack <int> St;

void Citire()
{
    int x, y;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void Componenta(int x, int y)
{
    Nrc++;
    while (St.top() != y)
    {
        Sol[Nrc].push_back(St.top());
        St.pop();
    }
    Sol[Nrc].push_back(y);
    Sol[Nrc].push_back(x);
    St.pop();
}

void DFS(int nod, int tata)
{
    int vecin;
    vector <int> :: iterator it;
    Nivel[nod] = Low[nod] = Nivel[tata] + 1;
    for (it = G[nod].begin(); it != G[nod].end(); ++it)
    {
        vecin = *it;
        if (vecin == tata)
            continue;
        if (!Nivel[vecin])
        {
            St.push(vecin);
            DFS(vecin, nod);
            Low[nod] = min(Low[nod], Low[vecin]);
            if (Low[vecin] >= Nivel[nod])
                Componenta(nod, vecin);
        }
        else Low[nod] = min(Low[nod], Low[vecin]);
    }
}

void Rezolvare()
{
    for (int i = 1; i <= N; ++i)
        if (!Nivel[i])
        {
            St.push(i);
            DFS(i, 0);
            St.pop();
        }
}

void Afisare()
{
    printf("%d\n", Nrc);
    for (int i = 1; i <= Nrc; ++i)
    {
        for (vector <int> :: iterator it = Sol[i].begin(); it != Sol[i].end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
}

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

    Citire();
    Rezolvare();
    Afisare();

    return 0;
}