Cod sursa(job #1928854)

Utilizator LaurIleIle Laurentiu Daniel LaurIle Data 16 martie 2017 20:10:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100005
using namespace std;

int n, m, nr, nrcmp;
vector <int> dfn (nmax, -1), low(nmax, -1);
vector <int> G[nmax];
vector <int> componente[nmax];
stack <pair <int, int> > stiva;

void read()
{
    ifstream f("biconex.in");
    f >> n >> m;
    for(int x, y; m; --m)
    {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    f.close();
}

void golire_stiva(int nod, int tata)
{
    ++nrcmp;
    int x, y;
    do
    {
        x = stiva.top().first; y = stiva.top().second;
        stiva.pop();
        componente[nrcmp].push_back(x), componente[nrcmp].push_back(y);

    } while(x != nod || y != tata);
}

void dfs(int nod, int tata)
{
    dfn[nod] = ++nr;
    low[nod] = nr;
    for(int i=0; i<G[nod].size(); ++i)
    {
        if(G[nod][i] == tata) continue;
        if(dfn[G[nod][i]] == -1)
        {
            stiva.push(make_pair(G[nod][i], nod));
            dfs(G[nod][i], nod);
            low[nod] = min(low[nod], low[G[nod][i]]);
            if(low[G[nod][i]] >= dfn[nod])
                golire_stiva(G[nod][i], nod);
        }
        else
        {
            low[nod] = min(low[nod], dfn[G[nod][i]]);
        }
    }
}

void out()
{
    ofstream g("biconex.out");
    g << nrcmp << '\n';
    for(int i=1; i<=nrcmp; ++i)
    {
        int dim = componente[i].size();
        sort(componente[i].begin(), componente[i].end());
        componente[i].erase(unique(componente[i].begin(), componente[i].end()), componente[i].end());
        for(int j=0; j<componente[i].size(); ++j)
            g << componente[i][j] << ' ';
        g << '\n';
    }
    g.close();
}

int main()
{
    read();
    dfs(1, 0);
    out();
    return 0;
}