Cod sursa(job #2786202)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 20 octombrie 2021 15:26:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.57 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;

class Graf {
    int n;
    int m;
    vector<int> v[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();
private:
    void dfs(int nod);
    void dfsSortare(int nod, vector<int> &noduriSortate);
    void dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s, vector<bool> &inStack,
                       vector< vector<int> > &componente, int &cnt);
};

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++) {
        v[ muchii[i].first ].push_back(muchii[i].second);
        if (!directed) {
            v[ muchii[i].second ].push_back(muchii[i].first);
        }
    }
}
int Graf :: nrComponenteConexe() {
    for (int i = 1; i <= n; i++) {
        viz[i] = false;
    }
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i);
        }
    }
    return nr;
}
void Graf :: dfs(int nod) {
    viz[nod] = true;
    for (int i = 0; i < v[nod].size(); i++) {
        if (!viz[ v[nod][i] ]) {
            dfs(v[nod][i]);
        }
    }
}
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 < v[nod].size(); i++) {
            int vecin = v[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;
    memset(viz, 0, sizeof(viz));
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsSortare(i, noduriSortate);
        }
    }
    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) {
    viz[nod] = true;
    for (int i = 0; i < v[nod].size(); i++) {
        int vecin = v[nod][i];
        if (!viz[vecin]) {
            dfsSortare(vecin, noduriSortate);
        }
    }
    noduriSortate.push_back(nod);
}

vector< vector<int> > Graf :: componenteTareConexe() {
    vector<int> level, low;
    vector<bool> inStack;
    memset(viz, 0, sizeof(viz));
    level.resize(n + 1);
    low.resize(n + 1);
    inStack.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);
        }
    }
    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) {

    viz[nod] = true;
    cnt++;
    level[nod] = low[nod] = cnt;
    s.push(nod);
    inStack[nod] = true;
    for (int i = 0; i < v[nod].size(); i++) {
        int vecin = v[nod][i];
        if (!viz[vecin]) {
            dfsTareConexe(vecin, level, low, s, inStack, componente, cnt);
        }
        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);
    }
}

int n, m;
pair<int, int> muchii[2000005];
ifstream fin ("ctc.in");
ofstream fout("ctc.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 -> componenteTareConexe();
    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";
    }
}