Cod sursa(job #1122199)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 25 februarie 2014 16:56:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>

#define Nmax 100005

using namespace std;

int N,M,nrbic;
vector<int> G[Nmax],sol[Nmax];
int niv[Nmax],low[Nmax];
stack<int> S;
bitset<Nmax> used;

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

void biconexa(int nodc,int nodn)
{
    ++nrbic;
    while(S.top() != nodn)
    {
        sol[nrbic].push_back(S.top());
        S.pop();
    }
    sol[nrbic].push_back(nodn);
    sol[nrbic].push_back(nodc);
    S.pop();
}

void DFS(int nodc,int daddy)
{
    used[nodc] = 1;
    niv[nodc] = niv[daddy] + 1;
    low[nodc] = niv[nodc];
    vector<int>::iterator it;
    for(it = G[nodc].begin(); it != G[nodc].end(); ++it)
    {
        if(*it == daddy)continue;
        if(!used[*it]){
            S.push(*it);
            DFS(*it,nodc);
            low[nodc] = min(low[nodc],low[*it]);
            if(niv[nodc] <= low[*it])
                biconexa(nodc,*it);
            continue;
        }
        low[nodc] = min(low[nodc],niv[*it]);
    }

}

void solve()
{
    for(int i = 1; i <= N; ++i)
        if(!used[i])
        {
            S.push(i);
            DFS(i,0);
            S.pop();
        }
}
void print()
{
    printf("%d\n",nrbic);
    for(int i = 1; i <= nrbic; ++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 );

    read    ();
    solve   ();
    print   ();

    return 0;
}