Cod sursa(job #2789627)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 27 octombrie 2021 18:52:38
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.32 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;

class Graf {
    int n;
    int m;
    vector<int> vecini[100002];
    bool viz[100002];
public:
    Graf(int n, int m, pair<int, int> muchii[], bool directed);
    int nrComponenteConexe();
    vector<int> bfs(int srs);
    vector<int> sortareTopologica();
    vector< vector<int> > componenteTareConexe();
    vector< vector<int> > componenteBiconexe();
private:
    void dfs(int nod, vector<bool> &viz);
    void dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz);
    void dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s, vector<bool> &inStack,
                       vector< vector<int> > &componente, int &cnt, vector<bool> &viz);
    void dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz);
};

Graf :: Graf(int n, int m, pair<int, int> muchii[], bool directed) {
    this->n = n;
    this->m = m;
    for (int i = 1; i <= m; i++) {
        vecini[ muchii[i].first ].push_back(muchii[i].second);
        if (!directed) {
            vecini[ muchii[i].second ].push_back(muchii[i].first);
        }
    }
}
int Graf :: nrComponenteConexe() {
    vector<bool> viz;
    viz.resize(n + 1);
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i, viz);
        }
    }
    return nr;
}
void Graf :: dfs(int nod, vector<bool> &viz) {
    viz[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        if (!viz[ vecini[nod][i] ]) {
            dfs(vecini[nod][i], viz);
        }
    }
}
vector<int> Graf :: bfs(int srs) {
    vector<int> dist;
    dist.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    queue<int> q;
    q.push(srs);
    dist[srs] = 0;
    while (!q.empty()) {
        int nod = q.front();
        for (int i = 0; i < vecini[nod].size(); i++) {
            int vecin = vecini[nod][i];
            if (dist[vecin] == -1) {
                dist[vecin] = dist[nod] + 1;
                q.push(vecin);
            }
        }
        q.pop();
    }
    return dist;
}

vector<int> Graf :: sortareTopologica() {
    vector<int> noduriSortate;
    vector<bool> viz;
    viz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsSortare(i, noduriSortate, viz);
        }
    }
    for (int i = 0; i < n / 2; i++) {
        swap(noduriSortate[i], noduriSortate[n - i - 1]);
    }
    return noduriSortate;
}

void Graf :: dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz) {
    viz[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!viz[vecin]) {
            dfsSortare(vecin, noduriSortate, viz);
        }
    }
    noduriSortate.push_back(nod);
}

vector< vector<int> > Graf :: componenteTareConexe() {
    vector<int> level, low;
    vector<bool> inStack, viz;
    level.resize(n + 1);
    low.resize(n + 1);
    inStack.resize(n + 1);
    viz.resize(n + 1);
    int cnt = 0;
    vector< vector<int> > componente;
    stack<int> s;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsTareConexe(i, level, low, s, inStack, componente, cnt, viz);
        }
    }
    return componente;
}

void Graf :: dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s,
                vector<bool> &inStack, vector< vector<int> > &componente, int &cnt, vector<bool> &viz) {

    viz[nod] = true;
    cnt++;
    level[nod] = low[nod] = cnt;
    s.push(nod);
    inStack[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!viz[vecin]) {
            dfsTareConexe(vecin, level, low, s, inStack, componente, cnt, viz);
        }
        if (inStack[vecin]) {
            low[nod] = min(low[nod], low[vecin]);
        }
    }
    if (low[nod] == level[nod]) {
        vector<int> noduriComponenta;
        int nodComponenta;
        do {
            nodComponenta = s.top();
            inStack[nodComponenta] = 0;
            s.pop();
            noduriComponenta.push_back(nodComponenta);
        } while (nodComponenta != nod);
        componente.push_back(noduriComponenta);
    }
}

vector< vector<int> > Graf :: componenteBiconexe() {
    vector<int> level, low;
    vector<bool>  viz;
    level.resize(n + 1);
    low.resize(n + 1);
    viz.resize(n + 1);
    vector< vector<int> > componente;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, viz);
    return componente;
}

void Graf:: dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz) {

    viz[nod] = 1;
    level[nod] = low[nod] = level[tata] + 1;
    s.push(nod);
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (vecin == tata) {
            continue;
        }
        if (viz[vecin] == 1) {
            low[nod] = min(low[nod], level[vecin]);
            continue;
        }
        dfsBiconexe(vecin, nod, level, low, s, componente, viz);
        low[nod] = min(low[nod], low[vecin]);
        if (low[vecin] >= level[nod]) {
            vector<int> componenta;
            componenta.push_back(nod);
            int nodComponenta;
            do{
                nodComponenta = s.top();
                componenta.push_back(nodComponenta);
                s.pop();
            } while (nodComponenta != vecin);
            componente.push_back(componenta);
        }
    }
}

int n, m;
pair<int, int> muchii[2000005];
ifstream fin ("biconex.in");
ofstream fout("biconex.out");
int main() {
    fin>> n >> m;
    for (int i = 1; i <= m; i++) {
        fin>> muchii[i].first >> muchii[i].second;
    }
    Graf* graf = new Graf(n, m, muchii, true);
    vector< vector<int> > componente = graf -> componenteBiconexe();
    fout<< componente.size() <<"\n";
    for (int i = 0; i < componente.size(); i++) {
        for (int j = 0; j < componente[i].size(); j++) {
            fout<< componente[i][j] <<" ";
        }
        fout<<"\n";
    }
}