Cod sursa(job #1146609)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 19 martie 2014 09:50:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.28 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#define MAX 100001
#define pb push_back
#define mp make_pair

using namespace std;

int N , M , low[MAX] , u[MAX] , niv[MAX] ,t[MAX], l[MAX] , k , nr , start ;
vector<int> G[MAX] ;
vector<int> Comp[MAX];
stack< pair<int,int> > ST;

void citire();
void solve();
void DF(int nod);
void Make_Comp(int nr,int x , int y);
void tipar();

int main()
{
    citire();
    solve();
    tipar();
    return 0;
}

void citire()
{
    int x, y;
    freopen("biconex.in" , "r" , stdin );
    scanf("%d%d" , &N , &M );
    for( int i = 1 ; i <= M; ++i )
    {
        scanf("%d%d" , &x , &y );
        G[x].pb(y);G[y].pb(x);
    }
}

void solve()
{
    for( int i = 1 ; i <= N ; ++i )
        if(!u[i])
        {
            u[i] = 1;
            niv[i] = 1;
            DF(i);
        }
}

void DF(int nod)
{
    u[nod] = 1;
    low[nod] = niv[nod];
    vector<int>::iterator it;
    for( it = G[nod].begin() ; it < G[nod].end() ; ++it)
    {
        if(*it != t[nod] && niv[nod] > niv[*it])
        ST.push(mp(nod,*it));
        if(!u[*it])
        {
            niv[*it] = niv[nod]+1;
            t[*it] = nod;
            DF(*it);
            if(low[*it] >= niv[nod] && ST.size())
                Make_Comp(++nr,nod,*it);
            if(low[*it] < low[nod])
                low[nod] = low[*it];
        }
        else
            if(low[nod] > niv[*it] && t[nod] != *it)
                low[nod] = niv[*it];
    }
}

void Make_Comp(int nr,int x , int y)
{
    pair<int,int> M1 = mp(x,y) , M2 = mp(y,x) , M = ST.top();
    while(M != M1 && M!=M2)
    {
        Comp[nr].pb(ST.top().second);Comp[nr].pb(ST.top().first);
        ST.pop();
        M = ST.top();
    }
    Comp[nr].pb(ST.top().second);Comp[nr].pb(ST.top().first);
    ST.pop();
}

void tipar()
{
    freopen("biconex.out" , "w" , stdout);
    printf("%d\n" , nr );
    vector<int>::iterator it;
    for( int i = 1 ; i <= nr ; ++i )
        {
            sort(Comp[i].begin(),Comp[i].end());
           Comp[i].erase(unique(Comp[i].begin(),Comp[i].end()),Comp[i].end());
           for(it = Comp[i].begin() ; it < Comp[i].end() ; ++it)
            printf("%d " , *it);
            printf("\n");
        }
}