Cod sursa(job #2796741)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 8 noiembrie 2021 19:14:05
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.41 kb
#include <bits/stdc++.h>

using namespace std;

//ifstream fin("dfs.in");
//ifstream fin("bfs.in");
//ifstream fin("sortaret.in");
ifstream fin("biconex.in");
ofstream fout("biconex.out");
//ofstream fout("sortaret.out");
//ofstream fout("bfs.out");
//ofstream fout("dfs.out");


class Graf {
private:
    static const int N = 100010;
    int n, m, nod_plecare;
    vector<int> v[N];
    vector<int> raspuns, Raspuns[N];
    int ans[N] = {0};
    int intoarcere[N] = {0}, nivel[N] = {0}, st[N] = {0};
    int top = 0, nr_sol = 0;
    queue<pair<int, int>> q;
    bitset<N> viz;

public:
    Graf();

    ~Graf();

    void add_edge(int, int);

    void dfs(int);

    void dfs_comp_bi(int, int);

    void afiseaza_componentele_biconexe();

    void bfs();

    void citire_Graf_neorientat();

    void citire_Graf_orientat();

    void citire_Graf_orientat_bfs();

    void sortare_topologica();

    int nr_connected_components();
};

Graf::Graf() {

}

Graf::~Graf() {

}

void Graf::add_edge(int x, int y) {
    v[x].push_back(y);
    v[y].push_back(x);
}

void Graf::dfs(int node) {
    viz[node] = 1;
    for (auto it: v[node])
        if (!viz[it])
            dfs(it);

    raspuns.push_back(node);
}

void Graf::dfs_comp_bi(int nod, int tata) {
    intoarcere[nod] = nivel[nod] = nivel[tata] + 1;
    viz[nod] = 1;
    top++;
    st[top] = nod;

    for (auto fiu: v[nod]) {
        if (fiu == tata)
            continue;
        if (viz[fiu]) { // suntem intr-o muchie de intoarcere
            intoarcere[nod] = min(intoarcere[nod], nivel[fiu]);
            continue;
        }
        dfs_comp_bi(fiu,nod);
        intoarcere[nod] = min(intoarcere[nod],nivel[fiu]);

            if (intoarcere[fiu] >= nivel[nod]) {
                nr_sol++;
                while (st[top + 1] != fiu) {
                    Raspuns[nr_sol].push_back(st[top]);
                    top--;
                }
                Raspuns[nr_sol].push_back(nod);
            }
        }
    }


void Graf::afiseaza_componentele_biconexe() {
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs_comp_bi(i, 0);

    fout << this->nr_sol << '\n';

    for (int i = 1; i <= nr_sol; i++) {
        for (auto it: Raspuns[i])
            fout << it << " ";
        fout << '\n';
    }

}

void Graf::sortare_topologica() {
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);

    for (vector<int>::reverse_iterator it = raspuns.rbegin(); it != raspuns.rend(); it++)
        fout << (*it) << " ";
}

int Graf::nr_connected_components() {
    int ct = 0;
    for (int i = 1; i <= this->n; i++)
        if (!viz[i]) {
            dfs(i);
            ct++;
        }
    return ct;
}

void Graf::citire_Graf_neorientat() {
    int nr_noduri, nr_muchii;
    fin >> nr_noduri >> nr_muchii;
    this->n = nr_noduri;
    this->m = nr_muchii;

    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void Graf::citire_Graf_orientat() {
    int nr_noduri, nr_muchii;
    fin >> nr_noduri >> nr_muchii;
    (*this).n = nr_noduri;
    (*this).m = nr_muchii;

    for (int i = 1; i <= (*this).m; i++) {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
    }
}

void Graf::citire_Graf_orientat_bfs() {
    int nr_noduri, nr_muchii, plecare;
    fin >> nr_noduri >> nr_muchii >> plecare;
    this->n = nr_noduri;
    this->m = nr_muchii;
    this->nod_plecare = plecare;

    q.push(make_pair(this->nod_plecare, 0));
    for (int i = 1; i <= this->m; i++) {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
    }
}

void Graf::bfs() {
    while (!q.empty()) {
        pair<int, int> dp = q.front();
        int x = dp.first;
        int y = dp.second;
        ans[x] = y;
        for (auto it: v[x])
            if (!viz[it]) {
                viz[it] = 1;
                q.push(make_pair(it, y + 1));
            }
        q.pop();
    }

    ans[this->nod_plecare] = 0;
    for (int i = 1; i <= n; i++) {
        if (ans[i] == 0 && i != this->nod_plecare)
            ans[i] = -1;
        fout << ans[i] << " ";
    }
}

int main() {
    /*
    Graf G;
    G.citire_Graf_neorientat();
    fout<<G.nr_connected_components();
    */

    /*
    Graf G;
    G.citire_Graf_orientat_bfs();
    G.bfs();
     */

    /*
    Graf G;
    G.citire_Graf_orientat();
    G.sortare_topologica();
     */

    Graf G;
    G.citire_Graf_neorientat();
    G.afiseaza_componentele_biconexe();
    return 0;
}