Cod sursa(job #1166264)

Utilizator darrenRares Buhai darren Data 3 aprilie 2014 13:31:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
int T[100002], niv[100002];
bool S[100002];
int mingo[100002];
int ST[100002];
int compnow;
vector<int> comps[100002];

void Dfs(int x)
{
    S[x] = true;
    ST[++ST[0]] = x;

    mingo[x] = niv[x];
    for (auto it = V[x].begin(); it != V[x].end(); ++it)
    {
        if (!S[*it])
        {
            T[*it] = x;
            niv[*it] = niv[x] + 1;
            Dfs(*it);
        }
        if (*it != T[x])
            mingo[x] = min(mingo[x], min(niv[*it], mingo[*it]));
    }

    if (mingo[x] == niv[x])
    {
        if (ST[ST[0]] != x)
        {
            ++compnow;
            while (true)
            {
                comps[compnow].push_back(ST[ST[0]]);
                --ST[0];
                if (ST[ST[0] + 1] == x) break;
            }
        }
        else
            --ST[0];

        if (T[x] != 0)
        {
            ++compnow;
            comps[compnow].push_back(T[x]);
            comps[compnow].push_back(x);
        }
    }
}

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

    scanf("%d %d", &N, &M);
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        scanf("%d %d", &nod1, &nod2);
        V[nod1].push_back(nod2);
        V[nod2].push_back(nod1);
    }

    Dfs(1);

    printf("%d\n", compnow);
    for (int i = 1; i <= compnow; ++i)
    {
        for (auto it = comps[i].begin(); it != comps[i].end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
}