Cod sursa(job #2659157)

Utilizator Vlad.Vlad Cristian Vlad. Data 15 octombrie 2020 22:19:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M, root;
int minNiv[NMAX], niv[NMAX];
vector<vector<int>> gr, comp;
stack<pair<int, int>> st;
void read() {
    fin >> N >> M;
    int x, y;
    gr.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        fin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
}
void addComponent(int x, int y) {
    pair<int, int> top;
    vector<int> v;
    do {
        top = st.top();
        st.pop();
        v.push_back(top.second);
    }while(!st.empty() && (top.first != x || top.second != y));
    v.push_back(top.first);
    comp.push_back(v);
}
void addRootComponent(int x) {
    vector<int> v;
    pair<int, int> top;
    do {
        top = st.top();
        st.pop();
        v.push_back(top.second);
    }while(!st.empty() && (top.first != x && top.second != x));
    v.push_back(top.first);
    comp.push_back(v);
}
void DFS(int node, int previousNode) {
    int nrF = 0;
    niv[node] = niv[previousNode] + 1;
    minNiv[node] = niv[node];
    for (int i : gr[node]) {
        if (niv[i] == 0) {
            ++nrF;
            st.emplace(node, i);
            DFS(i, node);
            minNiv[node] = min(minNiv[node], minNiv[i]);
            if (minNiv[i] >= niv[node] && node != root) {
                addComponent(node, i);
            }
        }
        else if(i != previousNode) {
            minNiv[node] = min(minNiv[node], niv[i]);
        }
    }
    if (nrF > 1 && node == root) {
        addRootComponent(root);
    }
}
int main()
{
    read();
    for (int i = 1; i <= N; ++i) {
        if (niv[i] == 0) {
            root = i;
            DFS(i, 0);
            if (!st.empty()) {
                vector<int> v;
                pair<int, int> top;
                while (!st.empty()) {
                    top = st.top();
                    st.pop();
                    v.push_back(top.second);
                }
                v.push_back(top.first);
                comp.push_back(v);
            }
        }
    }
    fout << comp.size() << "\n";
    for (int i = 0; i < comp.size(); ++i) {
        for (int j = comp[i].size() - 1; j >= 0; --j) {
            fout << comp[i][j] << " ";
        }
        fout << "\n";
    }
    return 0;
}