Cod sursa(job #1249621)

Utilizator gabrieligabrieli gabrieli Data 27 octombrie 2014 11:24:15
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <algorithm>
#include <fstream>
#include <iterator>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

vector<bool> visited;
stack<pair<int, int>> edges;
vector<vector<int>> bc, G;
vector<int> reach, level;

void dfs(const int v, const int pv, int lvl) {
    visited[v] = true;
    level[v] = reach[v] = lvl;
    
    for (int u : G[v]) {
        if (!visited[u]) {
            edges.push(make_pair(v, u));
            dfs(u, v, lvl+1);
            
            reach[v] = min(reach[v], reach[u]);
            
            if (reach[u] >= level[v]) {
                bc.push_back(vector<int>());
                pair<int, int> e;
                do {
                    e = edges.top(); edges.pop();
                    
                    bc.back().push_back(e.second + 1);
                } while (e.first != v && e.second != u);
                bc.back().push_back(v + 1);
            }
        }
        else if (u != pv)
            reach[v] = min(reach[v], reach[u]);
    }
} 

int main() {
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    
    int n, m; fin >> n >> m;
    
    G.resize(n);
    for (; m; --m) {
        int u, v;
        fin >> u >> v;
        
        G[u-1].push_back(v-1);
        G[v-1].push_back(u-1);
    }
    
    visited.resize(G.size(), false);
    reach.resize(G.size());
    level.resize(G.size());
    
    for (int v = 0; v < G.size(); ++v) if(!visited[v])
        dfs(v, -1, 0);
    
    fout << bc.size() << '\n';
    for (auto& c : bc) {
        copy(c.begin(), c.end(), ostream_iterator<int>(fout, " "));
        fout << '\n';
    }
    
    return 0;
}