Cod sursa(job #1974472)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 aprilie 2017 19:15:16
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;
const int Nmax = 100005;

vector<vector<int> > G, bix;
vector<int> depth, level;
bitset<Nmax> used;
int N, M, nrb;
stack<int> S;

void scoate(int k, int v)
{
    ++nrb;
    vector<int> b;
    while(S.top() != k) {
        int p = S.top(); S.pop();
            b.push_back(p);
    }
    b.push_back(k);
    bix.push_back(b);
}

void biconex(int k, int dad)
{
    used[k] = true;
    depth[k] = depth[dad] + 1;
    level[k] = depth[k];

        for(auto it : G[k])
        if(!used[it]) {
            S.push(it);
            biconex(it, k);

            level[k] = min(level[k], level[it]);
            if(level[it] >= depth[k])
                scoate(k, it);

        }
        else
            if(it != dad && depth[it] < level[k])
                level[k] = depth[it];
}


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

    scanf("%d%d", &N, &M);
    G.resize(N + 1);
    depth.resize(N + 1);
    level.resize(N + 1);

    for(int i = 1; i <= M; ++i) {
        int a,b;
        scanf("%d%d",&a ,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i <= N; ++i)
        if(!used[i]){
            S.push(i);
            biconex(i, 0);
        }
    printf("%d\n", bix.size());
    for(auto it : bix)
    {
        for(auto jt : it)
            printf("%d ",jt);
        printf("\n");
    }

    return 0;
}