Cod sursa(job #972456)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 11 iulie 2013 19:14:30
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 4 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

/**
    dfn[x] = numarul de ordine al varfului x la parcurgerea DFS a grafului (depth-first-number)
    low[x] = numarul de ordine al primului varf din parcurgerea DFS a grafului care poate fi atins pe un alt
             lant decat lantul unic din arborele partial DFS
    low[x] = min (dfn[x], min(low[y] | y este fiu al lui x), min(dfn[z] | [x, z] este muchie de intoarcere))
    S = stiva in care retinem muchiile atat pe cele din arborele DFS cat si pe cele de intoarcere in
        ordinea in care sunt intalnite in cadrul parcurgerii
*/

struct Muchie
{
    int x, y;
};
stack <Muchie> S;
Muchie auxx;
int dfn[100010];
int low[100010];
const int start = 1;
int n, m, nrc, num, nrfii;
vector <int> G[100010];
vector <int> comp[100010];

inline int min(int x, int y)
{
    return x<y?x:y;
}

inline void Read()
{
    ifstream f ("biconex.in");
    f>>n>>m;
    int i, x, y;
    for (i=1; i<=m; i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

inline void Initializare()
{
    int i;
    for (i=1; i<=n; i++)
        dfn[i] = low[i] = -1;
    Muchie aux;
    /**
        initializam stiva cu o muchie fictiva care in capete nodul 1 ca nod de start pentru DFS
        si nodul fictiv -1
    */
    aux.x = start;
    aux.y = -1;
    S.push(aux);
}

inline void CompBiconexa(int nod, int x)
{
    nrc++;
    Muchie p;
    int nr = 0;
    p = S.top();
    while (!(p.x == nod && p.y == x))
    {
        nr++;
        comp[nrc].push_back(p.y);
        S.pop();
        p = S.top();
    }
    if (nr == 0)
    {
        comp[nrc].push_back(nod);
        comp[nrc].push_back(x);
    }
    else
    {
        comp[nrc].push_back(x);
    }
    S.pop();
}


inline void Biconex(int nod, int tatanod)
{
    /// nod este nodul curent iar tatanod este tatal lui
    /// num ajuta la calcularea numarului de ordine al nodului curent in parcurgerea DFS
    num++;
    dfn[nod] = low[nod] = num;
    int x;
    vector <int>::iterator it;
    for (it = G[nod].begin(); it!=G[nod].end(); it++)
    {
        x = *it; /// x este nod adiacent al lui nod;
        /// daca x este diferit de tatal lui nod si daca x nu a mai fost vizitat sau
        /// a mai fost vizitat dar inaintea lui nod (este back edge)
        /// atunci muchia se adauga in stiva
        /// a 2a conditie este pusa pentru a nu adauga de 2 ori aceeasi muchie
        if (x != tatanod && dfn[x] < dfn[nod])
        {
            /// inseram in stiva S muchia [nod, x];
            auxx.x = nod;
            auxx.y = x;
            S.push(auxx);
        }
        if (dfn[x] == -1) /// daca adiacentul nu a mai fost vizitat
        {
            if (nod == start) /// am gasit pe x ca fiind fiu al nodului start
                nrfii++;
            Biconex(x, nod); /// facem DFS din x amu
            low[nod] = min(low[nod], low[x]);
            if (low[x] >= dfn[nod]) /// daca nod este punct de articulatie
            {
                /// am gasit o componenta biconexa formata din muchiile din stiva S pana la
                /// intalnirea muchiei [nod, x]
                CompBiconexa(nod, x);
            }
        }
        else
        {
            if (x != tatanod)
            {
                /// x nu este tatanod si x a mai fost vizitat ca de asta intra pe else
                /// atunci inseamna ca muchia [nod, x] este muchie de intoarcere de la nod la x
                low[nod] = min(low[nod], dfn[x]);
            }
        }
    }
}

inline void Write()
{
    ofstream g("biconex.out");
    g<<nrc<<"\n";
    int i;
    vector <int>::iterator it;
    for (i = 1; i<=nrc; i++)
    {
        for (it = comp[i].begin(); it!=comp[i].end(); it++)
            g<<*it<<" ";
        g<<"\n";
    }
    g.close();
}

int main()
{
    Read();
    Initializare();
    Biconex(start, -1); /// DFS (start, tatastart);
    Write();
    return 0;
}