Cod sursa(job #2107451)

Utilizator AurelGabrielAurel Gabriel AurelGabriel Data 17 ianuarie 2018 11:05:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;

long int n, m;
ifstream f("ctc.in");
ofstream g("ctc.out");

stack<long int> s, p;
long int* preorder;
long int c;
bool* assigned;

vector<vector<long int> > sol;

struct graph{
    vector<long int>* adj;
    long int num_nodes;

    graph(int nodes)
    {
        num_nodes = nodes;
        adj = new vector<long int>[num_nodes];
    }

    void add_edge(long int u, long int v)
    {
        adj[u].push_back(v);
    }

    void scc()
    {
        while(!s.empty()) s.pop();
        while(!p.empty()) p.pop();

        c = 0;

        if(preorder) delete[] preorder;
        preorder = new long int[num_nodes];
        memset(preorder, -1, sizeof(long int)* num_nodes);

        if(assigned) delete[] assigned;
        assigned = new bool[num_nodes];
        memset(assigned, 0, sizeof(bool)* num_nodes);

        for(long int i = 0; i < num_nodes; i++)
            if(!assigned[i])
                scc_dfs(i);
    }

    void scc_dfs(long int v)
    {
        preorder[v] = c++;
        s.push(v);
        p.push(v);

        for(size_t i = 0; i < adj[v].size(); i++)
        {
            long int w = adj[v][i];
            if(preorder[w] == -1)
                scc_dfs(w);
            else if(!assigned[w])
                while(preorder[p.top()] > preorder[w])
                    p.pop();
        }

        if(p.top() == v)
        {
            sol.push_back(vector<long int>());
            while(s.top()!= v)
            {
                sol.back().push_back(s.top()+1);
                assigned[s.top()] = true;
                s.pop();
            }
            sol.back().push_back(s.top()+1);
            assigned[s.top()] = true;
            s.pop();

            p.pop();
        }
    }
};



int main()
{
    f >> n >> m;
    graph gr(n);

    for(long int i = 0; i < m; i++)
    {
        long int u, v;
        f >> u >> v;
        gr.add_edge(u-1, v-1);
    }

    gr.scc();
    g << sol.size() << '\n';
    for(long int i = 0; i < sol.size(); i++)
    {
        for(long int j = 0; j < sol[i].size(); j++)
            g << sol[i][j] << ' ';
        g << '\n';
    }

    return 0;
}