Cod sursa(job #951559)

Utilizator mihai10stoicaFMI - Stoica Mihai mihai10stoica Data 20 mai 2013 22:30:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN  100005
#define Min(a, b)  ((a) < (b) ? (a) : (b))
vector <int> adj[MAXN], niv, nivint;
vector <vector <int> > C;
stack <pair <int, int> > stk;
void comp(const int x, const int y)
{
    vector <int> con; int tx, ty;
    do {
        tx = stk.top().first, ty = stk.top().second;
        stk.pop();
        con.push_back(tx), con.push_back(ty);
    }
    while (tx != x || ty != y);
    C.push_back(con);
}
void DF(const int n, const int fn, int number)
{
    vector <int>::iterator it;
    niv[n] = nivint[n] = number;
    for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
        if (*it == fn)   continue ;
        if (niv[*it] == -1) {
            stk.push( make_pair(n, *it) );
            DF(*it, n, number + 1);
            nivint[n] = Min(nivint[n], nivint[*it]);
            if (nivint[*it] >= niv[n])
                comp(n, *it);
        }
        else
            nivint[n] = Min(nivint[n], niv[*it]);
    }
}
int main(void)
{
    ifstream in("biconex.in");
    int n,m, x, y;
    in >> n >> m;
    while(m--)
    {
        in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    in.close();

    niv.resize(n + 1); niv.assign(n + 1, -1);
    nivint.resize(n + 1);
    DF(1, 0, 0);

    ofstream out("biconex.out");
    out << C.size() << "\n";
    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 << "\n";
    }
    out.close();
    return 0;
}