Cod sursa(job #2263796)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 19 octombrie 2018 11:47:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

#define NMAX 100001

vector <int> v[NMAX];
vector <vector <int> > sol;
int low[NMAX], lev[NMAX];
short viz[NMAX];
stack <pair <int, int> > st;

void bc(int nod, int x) {
    int a, b;
    vector <int> v;
    do {
        a = st.top().first;
        b = st.top().second;
        v.push_back(a);
        v.push_back(b);
        st.pop();
    } while (a != nod || x != b);
    sol.push_back(v);
}

void dfs(int nod, int niv, int p) {
    viz[nod] = 1;
    lev[nod] = niv;
    low[nod] = niv;
    for (const int x : v[nod]) {
        if (viz[x] == 0) {
            st.push(make_pair(nod, x));
            dfs(x, niv + 1, nod);
            low[nod] = min(low[nod], low[x]);
            if (low[x] >= niv) {
                bc(nod, x);
            }
        } else if (x != p) {
            low[nod] = min(low[nod], lev[x]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x,  y;
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    f.close();

    for (int i = 1; i <= n; i++) {
        if (viz[i] == 0)
            dfs(i, 0, 0);
    }

    g << sol.size() << '\n';
    for (vector <int>& v : sol) {
        sort(v.begin(), v.end());
        const int n = (int)v.size();
        g << v[0] << " ";
        for (int j = 1; j < n; j++) {
            if (v[j] != v[j - 1])
                g << v[j] << " ";
        }
        g << '\n';
    }
    g.close();

    return 0;
}