Cod sursa(job #492432)

Utilizator MariusMarius Stroe Marius Data 14 octombrie 2010 16:17:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const char iname[] = "biconex.in";
const char oname[] = "biconex.out";

const int MAX_N = 100005;

vector <int> adj[MAX_N], dfn, low;
stack < pair <int, int> > stk;
vector < vector <int> > cons;

void cache_bc(int x, int y) {
    pair <int, int> xy; vector <int> con;
    do {
        xy = stk.top();
        stk.pop();
        con.push_back(xy.first), con.push_back(xy.second);
    }
    while (xy.first != x || xy.second != y);
    cons.push_back(con);
}

void DF(int n, int fn, int number) {
    vector <int>::iterator it;

    dfn[n] = low[n] = number;
    for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
        if (*it == fn)  continue ;
        if (!dfn[*it]) {
            stk.push(make_pair(n, *it));
            DF(*it, n, number + 1);
            low[n] = min(low[n], low[*it]);
            if (low[*it] >= dfn[n])
                cache_bc(n, *it);
        } else
            low[n] = min(low[n], dfn[*it]);
    }
}

int main(void) {
    int nodes, edges, x, y;
    ifstream in(iname);
    in >> nodes >> edges;
    while (edges --) {
        in >> x >> y;
        adj[x - 1].push_back(y - 1);
        adj[y - 1].push_back(x - 1);
    }
    in.close();

    dfn.resize(nodes), dfn.assign(dfn.size(), 0);
    low.resize(nodes);
    DF(0, -1, 1);

    ofstream out(oname);
    out << cons.size() << '\n';
    for (size_t i = 0; i < cons.size(); ++ i) {
        sort(cons[i].begin(), cons[i].end());
        cons[i].erase(unique(cons[i].begin(), cons[i].end()), cons[i].end());
        for (size_t j = 0; j < cons[i].size(); ++ j)
            out << (cons[i][j] + 1) << " ";
        out << '\n';
    }
    out.close();

    return 0;
}