Cod sursa(job #2126117)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 9 februarie 2018 10:47:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 100005

using namespace std;

int N, M, indexGlobal = 1;
struct nod
{
    int index, lowlink;
}v[NMAX];
vector <vector <int> > sol;
vector <int> G[NMAX];
stack <pair <int, int> > S;

void read()
{
    scanf("%d %d", &N, &M);
    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);
    }
}

void adaugareComponenta(int node)
{
    vector <int> componenta;
    while(S.top().second != node)
    {
        componenta.push_back(S.top().second);
        S.pop();
    }
    componenta.push_back(S.top().second);
    componenta.push_back(S.top().first);
    S.pop();
    sol.push_back(componenta);
}

void dfs(int node, int tata)
{
    v[node].index = v[node].lowlink = indexGlobal;
    indexGlobal++;
    vector <int>::iterator it;
    for(it = G[node].begin(); it != G[node].end(); ++it)
    {
        if(*it == tata)
            continue;
        if(v[*it].index == 0)
        {
            S.push(make_pair(node, *it));
            dfs(*it, node);
            v[node].lowlink = min(v[node].lowlink, v[*it].lowlink);
            if(v[*it].lowlink >= v[node].index)
                adaugareComponenta(*it);
        }
        else
            v[node].lowlink = min(v[node].lowlink, v[*it].index);
    }
}

void solve()
{
    for(int i=1; i<=N; ++i)
        if(v[i].index == 0)
            dfs(i, 0);
}

void print()
{
    printf("%d\n", sol.size());
    vector <vector <int> >::iterator itSol;
    for(itSol = sol.begin(); itSol != sol.end(); ++itSol)
    {
        vector <int>::iterator it;
        for(it = itSol->begin(); it != itSol->end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    read();
    solve();
    print();
    return 0;
}