Cod sursa(job #3292205)

Utilizator ATudorAAparaschivei Tudor Andrei ATudorA Data 7 aprilie 2025 14:48:48
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.22 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector <int> v[100003];
stack <int> st;

vector <int> rez[100003];

int niv[100003];
int up[100003];
bool viz[100003];

int n, m, cnt;

void citire() {
    int i, x, y;

    f >> n >> m;

    for (i = 1; i <= m; i++) {
        f >> x >> y;

        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void afisare() {
    int i, j;

    g << cnt << '\n';

    for (i = 1; i <= cnt; i++) {
        for (j = 0; j < rez[i].size(); j++)
            g << rez[i][j] << " ";

        g << '\n';
    }
}

void DFS(int nod, int tata) {
    int i, urm;

    st.push(nod);

    viz[nod] = 1;
    niv[nod] = niv[tata] + 1;
    up[nod] = niv[nod];

    for (i = 0; i < v[nod].size(); i++) {
        urm = v[nod][i];

        if (urm == tata) continue;

        if (viz[urm] == 1) {
            up[nod] = min(up[nod], niv[urm]);
        }
        else {
            DFS(urm, nod);

            if (up[urm] >= niv[nod]) {
                cnt ++;

                while (st.top() != nod) {
                    rez[cnt].push_back(st.top());

                    st.pop();
                }

                rez[cnt].push_back(st.top());
            }

            up[nod] = min(up[nod], up[urm]);
        }
    }
}

int main()
{
    citire();

    niv[0] = 0;

    DFS(1, 0);

    afisare();

    return 0;
}

/**
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

vector <int> v[100003];
stack <pair <int, int> > st;

set <int> rez[100003];

int niv[100003];
int up[100003];
bool viz[100003];

int n, m, cnt;

void citire() {
    int i, x, y;

    f >> n >> m;

    for (i = 1; i <= m; i++) {
        f >> x >> y;

        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void afisare() {
    int i, j;

    g << cnt << '\n';

    for (i = 1; i <= cnt; i++) {
        for (j = 0; j < rez[i].size(); j++)
            g << rez[i][j] << " ";

        g << '\n';
    }
}

void DFS(int nod, int tata) {
    int i, urm, ok = 1;

    viz[nod] = 1;
    niv[nod] = niv[tata] + 1;
    up[nod] = niv[nod];

    for (i = 0; i < v[nod].size(); i++) {
        urm = v[nod][i];

        if (urm == tata) continue;

        if (viz[urm] == 1) {
            up[nod] = min(up[nod], niv[urm]);
        }
        else {
            st.push({nod, urm});

            DFS(urm, nod);

            if (up[urm] >= niv[nod]) {
                cnt ++;

                while (st.top().first != nod && st.top().second != urm) {
                    rez[cnt].insert(st.top().first);
                    rez[cnt].insert(st.top().second);

                    st.pop();
                }

                rez[cnt].insert(st.top().first);
                rez[cnt].insert(st.top().second);

                st.pop();
            }

            up[nod] = min(up[nod], up[urm]);
        }
    }
}

int main()
{
    citire();

    niv[0] = 0;

    DFS(1, 0);

    g << '\n';

    afisare();


    return 0;
}

*/