Cod sursa(job #1937216)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 23 martie 2017 20:04:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 100005
#include <vector>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
vector < int > a[NMAX];
vector < pair < int, int > > st;
vector < vector < int > > sol;
int dist[NMAX], mdist[NMAX], n, m;
inline int min(const int & a, const int & b) {
    if (a < b) return a;
    return b;
}

void Comp(const int & x, const int & y) {
    int a, b;
    vector < int > v, w;
    v.push_back(0);
    do {
        a = st.back().first;
        b = st.back().second;
        st.pop_back();
        v.push_back(a);
        v.push_back(b);
    } while (a != x || b != y);
    sort(v.begin(), v.end());
    for (int i = 1; i < v.size(); i++)
        if (v[i] != v[i - 1]) w.push_back(v[i]);
    sol.push_back(w);
}

void DF (int nod, int father, int level) {
    dist[nod] = mdist[nod] = level;
    for (int i = 0; i < a[nod].size(); i++) {
        if (a[nod][i] == father) continue;
        int it = a[nod][i];
        if (!dist[it]) {
            st.push_back(make_pair(nod, it));
            DF(it, nod, level + 1);
            mdist[nod] = min(mdist[nod], mdist[it]);
            if (mdist[it] >= dist[nod])
                Comp(nod, it);
        }
        else mdist[nod] = min(mdist[nod], dist[it]);
    }
}

int main()
{
    f>>n>>m;
    while (m--) {
        int x, y;
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    DF(1, 0, 1);
    g<<sol.size()<<'\n';
    for (int i = 0; i < sol.size(); i++) {
        for (int j = 0; j < sol[i].size(); j++)
            g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}