Cod sursa(job #1167009)

Utilizator darrenRares Buhai darren Data 4 aprilie 2014 10:22:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

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

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

    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;
            ST[++stsize] = make_pair(x, *it);

            Dfs(*it);

            if (mingo[*it] >= niv[x])
            {
                ++compnow;

                while (true)
                {
                    pair<int, int> now = ST[stsize];
                    comps[compnow].insert(now.first);
                    comps[compnow].insert(now.second);
                    --stsize;

                    if (now.first == x && now.second == *it)
                        break;
                }
            }

            mingo[x] = min(mingo[x], mingo[*it]);
        }
        else
            mingo[x] = min(mingo[x], niv[*it]);
    }
}

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");
    }
}