Cod sursa(job #2672033)

Utilizator SirbuSirbu Ioan Sirbu Data 12 noiembrie 2020 22:42:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

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

int viz[100002];
int low[100002];
int ind;
bool s[100002], c[100002];

vector <int> g[100002];
vector <int> sol[100002];
stack <int> st;

void DFS(int node, int &niv) {
    niv = niv + 1;
    viz[node] = niv;
    low[node] = niv;
    s[node] = 1;
    st.push(node);
    for (int i = 0; i < g[node].size(); ++i) {
        int nou = g[node][i];
        if (!viz[nou]) {
            DFS(nou, niv);
            low[node] = min(low[node], low[nou]);
            if (viz[node] <= low[nou]) {
                ind++;
                while(st.top()!= nou) {
                    s[st.top()] = 0;
                    sol[ind].push_back(st.top());
                    st.pop();
                }
                sol[ind].push_back(nou);
                sol[ind].push_back(node);
                s[nou] = 0;
                st.pop();
            }
        }
        else if (s[nou])
            low[node] = min(low[node], viz[nou]);
    }
}

int main() {

    int n, m, x, y;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int niv = 0;
    DFS(1, niv);

    fout << ind << '\n';
    for (int i = 1; i <= ind; ++i) {
        for (int j = 0; j < sol[i].size(); ++j)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
    return 0;
}