Cod sursa(job #1647813)

Utilizator gerd13David Gergely gerd13 Data 10 martie 2016 22:11:33
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <algorithm>
#include <vector>


using namespace std ;

const int NMAX = 100005 ;

ifstream fin("biconex.in") ;
ofstream fout("biconex.out");

int N, M, sol;
vector <int> V[NMAX], SOL[NMAX] ;
int lvl[NMAX] ;
int low[NMAX], st[NMAX], top;

void Biconex(int start, int finnish)
{
    sol ++ ;

    while(st[top] != finnish)
    {
        SOL[sol].push_back(st[top]) ;
        top -- ;
    }

    top -- ;
    SOL[sol].push_back(finnish) ;
    SOL[sol].push_back(start) ;

}

void DFS(int node)
{
    low[node] = lvl[node] ;
    top ++ ;

    st[top] = node ;

    for(int i = V[node].size() - 1 ; i >= 0 ; i --)
    {
        if(lvl[V[node][i]] == 0)
        {

            lvl[V[node][i]] = lvl[node] + 1 ;
            DFS(V[node][i]) ;

            if(low[V[node][i]] >= lvl[node])
                Biconex(node, V[node][i]) ;
        }
    }

    for(int i = V[node].size() - 1 ; i >= 0 ; i --)
        if(low[V[node][i]] < low[node])
            low[node] = low[V[node][i]] ;
}


int main()
{
    fin >> N >> M ;

    for(int i = 1 ; i <= M ; ++ i)
    {
        int x, y ;
        fin >> x >> y ;
        V[x].push_back(y) ;
        V[y].push_back(x) ;
    }

    lvl[1] = 1 ;
    top = 0 ;
    DFS(1) ;

    fout << sol << '\n';

    for(int i = 1 ; i <= sol ; ++ i)
    {
        sort(SOL[i].begin(), SOL[i].end()) ;

        for(vector <int> ::iterator it = SOL[i].begin(); it != SOL[i].end() ; ++ it)
            fout << *it << ' ' ;
        fout << '\n' ;
    }


    fin.close();
    fout.close() ;
    return 0 ;
}