Cod sursa(job #2671238)

Utilizator TraianVVisan Traian-Dimitrie TraianV Data 11 noiembrie 2020 19:34:16
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

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

#define Min(a, b)  ((a) < (b) ? (a) : (b))

vector <int> adj[100005], dfn, low;

vector <vector <int> > C;

stack <pair <int, int> > stv;

void read_in(vector <int>* adj, int &n)
{
    int i, x, y;
    in >> n >> i;
    for (; i > 0;  i--) {
        in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    in.close();
}

void cache_bc(int x, int y)
{
    vector <int> aux;
    int tx, ty;
    do {
        tx = stv.top().first, ty = stv.top().second;
        stv.pop();
        aux.push_back(tx), aux.push_back(ty);
    }
    while (tx != x || ty != y);
    C.push_back(aux);
}

void DF(int n, int fn, int number)
{
    vector <int>::iterator i;
    dfn[n] = low[n] = number;
    for (i = adj[n].begin();   i != adj[n].end(); i++) {
        if (*i == fn)   continue ;
        if (dfn[*i] == -1) {
            stv.push( make_pair(n, *i) );
            DF(*i, n, number + 1);
            low[n] = Min(low[n], low[*i]);
            if (low[*i] >= dfn[n])
                cache_bc(n, *i);
        }
        else
            low[n] = Min(low[n], dfn[*i]);
    }
}

int main()
{
    int n;
    read_in(adj,n);
    dfn.resize(n + 1);
    dfn.assign(n + 1, -1);
    low.resize(n + 1);
    DF(1, 0, 0);
    out << C.size() <<endl;
    for(int i = 0; i < C.size(); i++)
    {
        sort(C[i].begin(), C[i].end());
        C[i].erase( unique( C[i].begin(), C[i].end()    ), C[i].end()   );
        for (int j = 0;     j < C[i].size() ; j++)
            out << C[i][j] << " ";
        out << endl;
    }
    out.close();
    return 0;
}