Cod sursa(job #2796798)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 8 noiembrie 2021 19:52:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.84 kb
#include <bits/stdc++.h>

using namespace std;

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


const int N = 100010;

vector<int> nxt[N], prv[N], TOP;
int viz_1[N], viz_2[N];  // pentru componente tare conexe

class Graf {
private:

    int n, m, nod_plecare;
    vector<int> v[N];
    vector<int> raspuns, Raspuns[N]; // folosite pentru a memora raspunsurile problemelor
    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_1(int);

    void dfs_2(int);

    void dfs_comp_bi(int, int);

    void afiseaza_componentele_biconexe();

    void afiseaza_componentele_tare_conexe();

    void bfs();

    void citire_Graf_neorientat();

    void citire_Graf_orientat();

    void citire_Graf_orientat_tare_conexitate();

    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_1(int node) {
    viz_1[node] = 1;
    for(auto it: nxt[node])
        if(!viz_1[it])
            dfs_1(it);
    TOP.push_back(node);
}

void Graf::dfs_2(int node){
    viz_2[node] = 1;

    Raspuns[nr_sol].push_back(node);

    for(auto it:prv[node])
        if(!viz_2[it])
            dfs_2(it);
}

void Graf::afiseaza_componentele_tare_conexe() {
    for(int i=1;i<=n;i++)
        if(!viz_1[i])
            dfs_1(i);

    reverse(TOP.begin(),TOP.end());

    for(auto it:TOP)
        if(!viz_2[it])
        {
            nr_sol++;
            dfs_2(it);
        }

    fout<<nr_sol;

        for(const auto &it:Raspuns)
        {
            for(auto elem:it)
                fout<<elem<<" ";
            fout<<'\n';
        }
}

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], intoarcere[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::citire_Graf_orientat_tare_conexitate() {
    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;
        nxt[x].push_back(y);
        prv[y].push_back(x);

    }
}

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();
     */

    Graf G;
    G.citire_Graf_orientat_tare_conexitate();
    G.afiseaza_componentele_tare_conexe();

    return 0;
}