Cod sursa(job #2824321)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 1 ianuarie 2022 17:33:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.54 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");


bool sorta(pair<int, int> a, pair<int, int> b)
{
    if(a.first > b.first)
        return 0;
    return 1;
}

vector<int> returnVector(int n, int fillWith){
    vector<int> x;
    x.resize(n + 1);
    std::fill(x.begin(), x.end(), fillWith);
    return x;
}

class Graph{

private:
    vector< vector<int> > listaAdiacenta;
    vector<vector<int>  > listaAdiacentaT;
    vector<int> vizitat;
    vector<pair<int, int> > vizitatT;
    stack < int > Stiva;
    int n;
public:
    Graph(int n1) : n(n1){
        this->listaAdiacenta.resize(n1 + 1);
        this->listaAdiacentaT.resize(n1 + 1);
        this->vizitat.resize(n1 + 1);
        this->vizitatT.resize(n1 + 1);
    };

    void adaugMuchie(int deLa, int la){
        this->listaAdiacenta[deLa].push_back(la);
    }

    void adaugMuchieT(int deLa, int la){
        this->listaAdiacentaT[deLa].push_back(la);
    }

    void dfs(int varf){
        vizitat[varf] = true;
        for (int p: listaAdiacenta[varf]) {
            if(!vizitat[p]){
                dfs(p);
            }
        }
    }

    void dfs1(int varf){
        vizitat[varf] = 1;
        for (int p: listaAdiacenta[varf]) {
            if(!vizitat[p]){
                dfs1(p);
            }
        }
        Stiva.push(varf);
    }

    void dfs2(int varf, int contorComp){
        vizitatT[varf].first = contorComp;
        vizitatT[varf].second = varf;
        for (int p: listaAdiacentaT[varf]) {
            if(!vizitatT[p].first){
                dfs2(p, contorComp);
            }
        }
    }

    int nrComponenteConexe(){

        int contor = 0;
        for(int i = 1;i<=n;++i){
            if(!vizitat[i]){
                ++contor;
                dfs(i);
            }
        }

        return contor;

    }

    void print(){
        for (int i = 1; i <= n; i++)
        {
            // print the current vertex number
            cout << i << " ---> ";

            // print all neighboring vertices of a vertex `i`
            for (int v: listaAdiacenta[i]) {
                cout << v << " ";
            }
            cout << endl;
        }
    }

    void bfs(int startNo){

        int prim, ultim, i;
        queue <int> q;
        q.push(startNo);

        vizitat[startNo] = 1;

        while (!q.empty()){
            int nodAcutal = q.front();
            q.pop();
            for (int p: listaAdiacenta[nodAcutal]) {

                if(vizitat[p] == 0){
                    vizitat[p] = vizitat[nodAcutal] + 1;
                    q.push(p);
                }

            }
        }
    }

    void afisareVizitat(){
        for(int i = 1;i<=n;++i)fout<<vizitat[i] - 1<<" ";
    }

    void componenteTare(){


        for(int i = 1;i<=n;++i){
            if(!vizitat[i]){
                dfs1(i);
            }
        }

        int contorComp = 0;
        while(!Stiva.empty()){

            int varf = Stiva.top();
            Stiva.pop(); /// nu l mai folosim
            if(!vizitatT[varf].first){
                contorComp++;
                dfs2(varf, contorComp);
            }
        }

        fout<<contorComp<<endl;
        int cnt=1;
        sort(vizitatT.begin() + 1, vizitatT.end(), sorta);


        for(int i=1;i<=n;i++)
        {
            if(vizitatT[i].first > cnt)
            {
                fout<<'\n';
                cnt++;
            }
            if(vizitatT[i].first == cnt)
                fout<<vizitatT[i].second<<' ';
        }


    }

    void sscDfs(int startNode, int n, int &id, stack<int> &stack, vector<int> &onStack, vector<int> &low, vector<int> &ids, vector<vector<int>> &sscComponents){
        stack.push(startNode);
        onStack[startNode] = 1;
        ids[startNode] = low[startNode] = ++id;

        for(int vertex: this->listaAdiacenta[startNode]){
            if(ids[vertex] == 0) this->sscDfs(vertex, n, id, stack, onStack, low, ids, sscComponents);
            if(onStack[vertex]){
                int minim = (low[startNode] < low[vertex] ? low[startNode] : low[vertex]);
                low[startNode] = minim;
            }
        }
        if(ids[startNode] == low[startNode]){
            vector<int> elements;
            while(stack.top()){
                int vertex = stack.top();
                stack.pop();

                onStack[vertex] = 0;
                low[vertex] = ids[startNode];
                elements.push_back(vertex);
                if(vertex == startNode) {
                    break;
                }
            }
            sscComponents.push_back(elements);
        }
    }

    void getSSCComponents(){
        // unvisited is 0
        int id = 0;
        int sscCounter = 0;
        vector<int> ids = returnVector(this->n, 0);
        vector<int> low = returnVector(this->n, 0);
        vector<int> onStack = returnVector(this->n, 0);
        vector<vector<int>> sscComponents;
        stack<int> stack;
        for(int i = 1;i<=n;++i){
            if(ids[i] == 0){
                this->sscDfs(i, this->n, id, stack, onStack, low, ids, sscComponents);
            }
        }
        fout<<sscComponents.size()<<endl;
        for(int i = 0; i < sscComponents.size() ;++i){
            for(int element: sscComponents[i]){
                fout<<element<<" ";
            }
            fout<<"\n";
        }
    }


};

int main()
{
    int n, m;
    fin>>n>>m;
    Graph g(n);
    for(int i = 1;i<=m;++i){
        int a, b;
        fin>>a>>b;
        g.adaugMuchie(a, b);;
    }
    g.getSSCComponents();
    return 0;
}