Cod sursa(job #2686490)

Utilizator rareshinnhoMiroiu Rares rareshinnho Data 19 decembrie 2020 11:16:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int n, m, i, j, ord[100005], niv_min[100005];
bool viz[100005];
vector<int> v[100005], t(100005, -1);
vector<vector<int> > comp;
stack<int> st;

void dfs(int nod) {
    int it, x;
    vector<int> c;

    viz[nod] = true;
    ord[nod] = ord[t[nod]] + 1;
    niv_min[nod] = ord[nod];
    st.push(nod);
    for(it = 0; it < v[nod].size(); it++)
        if(viz[v[nod][it]]) {
            if(v[nod][it] != t[nod])
                niv_min[nod] = min(niv_min[nod], ord[v[nod][it]]);
        }
        else {
            t[v[nod][it]] = nod;
            dfs(v[nod][it]);
            niv_min[nod] = min(niv_min[nod], niv_min[v[nod][it]]);
            if(ord[nod] <= niv_min[v[nod][it]]) {
                c.clear();
                while(!st.empty()) {
                    x = st.top();
                    st.pop();
                    c.push_back(x);
                    if(x == v[nod][it]) {
                        c.push_back(nod);
                        comp.push_back(c);
                        break;
                    }
                }
            }
        }
}

int main() {
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    f >> n >> m;
    while(m) {
        f >> i >> j;

        v[i].push_back(j);
        v[j].push_back(i);
        m--;
    }
    for(i = 1; i <= n; i++)
        if(!ord[i]) {
            t[i] = 0;
            dfs(i);
        }

    g << comp.size() << '\n';
    for(i = 0; i < comp.size(); i++, g << '\n')
        for(j = 0; j < comp[i].size(); j++)
            g << comp[i][j] << ' ';
    return 0;
}