Cod sursa(job #2052033)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 29 octombrie 2017 21:26:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

class graf
{
    public:
        vector<vector<int> > vecini;
        graf(int n = 0)
        {
            this->n = n;
            vecini.resize(n + 1);
            viz.resize(n + 1);
        }
        void AddEdge(int x, int y)
        {
            vecini[x].push_back(y);
        }
        void GetStrongComp(vector<vector<int> > &ret)
        {
            for(int i = 1; i <= n; ++i)
                viz[i] = false;
            for(int i = 1; i <= n; ++i)
                if(viz[i] == false)
                    DFS(i);
            graf tr; //graful transpus
            GetTranspose(tr);
            for(int i = 1; i <= n; ++i)
                viz[i] = false;

            while(st.empty() == false)
            {
                int p = st.top();
                st.pop();

                if(!viz[p])
                {
                    vector<int> comp;
                    GetArb(comp, tr, p);
                    ret.push_back(comp);
                }
            }
        }
    private:
        void DFS(int current)
        {
            viz[current] = true;
            for(auto v:vecini[current])
                if(!viz[v])
                    DFS(v);
            st.push(current);
        }
        void GetTranspose(graf &ret)
        {
            ret = graf(n);
            for(int i = 1; i <= n; ++i)
                for(auto v:vecini[i])
                    ret.AddEdge(v, i);
        }
        void GetArb(vector<int> &ret, const graf &gr, int current)
        {
            viz[current] = true;
            ret.push_back(current);
            for(auto v:gr.vecini[current])
                if(!viz[v])
                    GetArb(ret, gr, v);
        }
        int n;
        vector<bool> viz;
        stack<int> st;
};

int main()
{
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    int n, m;
    in >> n >> m;
    graf gr(n);
    int x, y;
    while(m--)
    {
        in >> x >> y;
        gr.AddEdge(x, y);
    }
    vector<vector<int> > rasp;
    gr.GetStrongComp(rasp);
    out << rasp.size() << "\n";
    for(auto &v:rasp)
    {
        for(auto nod:v)
            out << nod << " ";
        out << "\n";
    }
    in.close();
    out.close();
    return 0;
}