Cod sursa(job #959738)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 8 iunie 2013 17:08:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define N_MAX 100010
vector<int> G[N_MAX];
stack<pair <int, int> > S;
vector<vector<int> > ctc;
int L[N_MAX], up[N_MAX];
int viz[N_MAX];

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

int n, m;
int my_time;
void dfs(int x, int father) {
    viz[x] = 1;
    up[x] = L[x] = ++my_time;
    for(auto &nod : G[x]) {
        if(nod == father) continue;

        if(!viz[nod]) {
            S.push(make_pair(x, nod));
            //L[nod] = L[x] + 1;
            dfs(nod, x);
            up[x] = min(up[x], up[nod]);

            if(up[nod] >= L[x]) { //critic
                vector<int> v;
                while(!S.empty() ) {
                    auto p = S.top();
                    S.pop();
                    v.push_back(p.first);
                    v.push_back(p.second);
                    if(p.first == x && p.second == nod) break;
                }
                ctc.push_back(v);
            }
        }
        else {
            up[x] = min(up[x], L[nod]);
        }
    }
}
int main() {
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);

    }
    for(int i = 1; i <= n; i++) {
        if(!viz[i]) {
            dfs(i, -1);
        }
    }
    fout << ctc.size() << "\n";
    for(size_t i = 0; i < ctc.size(); i++) {
        vector<int> &v = ctc[i];
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(),v.end()), v.end());
        for(int &x : v) {
            fout << x << " ";
        }
        fout << "\n";
    }
    return 0;
}