Cod sursa(job #837960)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 18 decembrie 2012 21:13:02
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_SIZE 100000
#include <algorithm>

using namespace std;

vector <int> graf[MAX_SIZE+1];
stack <int> parcurgere;
vector <int> biconexe[MAX_SIZE +1];
int tati[MAX_SIZE + 1];
int sel[MAX_SIZE+1];
int level[MAX_SIZE + 1];
int N , M ,nr = 0;



void create_component(int nod)
{
    nr++;
    while (parcurgere.top() != nod)
    {
        biconexe[nr].push_back(parcurgere.top());
        parcurgere.pop();
    }
    biconexe[nr].push_back(parcurgere.top());

    sort(biconexe[nr].begin(), biconexe[nr].end());


}

void DF(int nod , int nivel)
{
    sel[nod] = nivel;
    level[nod] = nivel;
    parcurgere.push(nod);
    for (int i = 0;i<graf[nod].size();i++)
    {
        int x = graf[nod][i];
        if (sel[x] == -1)
        {

            tati[x] = nod;
            DF(x ,  nivel + 1);
            sel[nod] = min(sel[nod],sel[x]);
            if ( sel[x] >= level[nod])
            {
                create_component(nod);
            }
        }
        else
        {
            if ( tati[nod] != x)
            {
                sel[nod] = min(sel[nod],level[x]);
            }
        }

    }

}



int main()
{
    ifstream input("biconex.in");
    ofstream output("biconex.out");
    input >> N >> M;
    for (int i =0;i<M;i++)
    {
        int x , y;
        input >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for (int i =0;i<=MAX_SIZE;i++)
    {
        sel[i] = -1;
    }

    for (int i =1;i<=N;i++)
    {
        if (sel[i] == -1)
        {
            DF(i,1);
        }
    }

    output << nr;
    for (int i =1;i<=nr;i++)
    {
        output << "\n";
        for (int j =0;j<biconexe[i].size();j++)
        {
            output << biconexe[i][j] << " ";
        }
    }
    input.close();
    output.close();
    return 0;
}