Cod sursa(job #2905386)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 21 mai 2022 11:54:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.16 kb
#include <bits/stdc++.h>

using namespace std;
const int dim = 50005;


template <class T>
class Graph
{
private:
    int node_count, edge_count;
    vector <T> adj[dim];
    vector <T> r_adj[dim];
public:
    Graph ()
    {
        node_count = 0;
        edge_count = 0;
    }
    void Make_Graph (int nodes, int edges)
    {
        node_count = nodes;
        edge_count = edges;
    }
    void Add_edge (int node1, int node2)
    {
        adj[node1].push_back(node2);
    }
    void Add_reverse_edge (int node1, int node2)
    {
        r_adj[node2].push_back(node1);
    }
    void Add_weighted_edge(int node1, int node2, int weight)
    {
        adj[node1].push_back({node2, weight});
    }
    int NodeNumber ()
    {
        return node_count;
    }
    void Afis_Graph ()
    {
        for (int i = 1; i <= node_count; i++, cout << "\n")
        {
            cout << i << ": ";
            for (int j : adj[i])
                cout << j << " ";
        }
    }
    void DFS_SortTop (int node, vector <int> &viz, stack <int> &st)
    {
        viz[node] = 1;
        for (int i : adj[node])
            if (!viz[i])
                DFS_SortTop(i, viz, st);
        st.push(node);
    }
    void DFS_SCC (int node, vector <int> &viz, vector <int> scc[dim], int nrscc)
    {
        viz[node] = 0;
        for (int i : r_adj[node])
            if (viz[i])
                DFS_SCC(i, viz, scc, nrscc);
        scc[nrscc].push_back(node);
    }
    stack <int> SortTop (vector <int> &viz, stack <int> &st)
    {
        for (int i = 1; i <= node_count; i++)
            if (!viz[i])
            {
                DFS_SortTop(i, viz, st);
            }
        return st;
    }
    void SCC(vector <int> &viz, stack <int> &st)
    {
        int nrscc = 0;
        stack <int> sol = SortTop(viz, st);
        vector <int> scc[dim];
        while (!sol.empty())
        {
            int node = sol.top();
            sol.pop();
            if (viz[node] == 1)
            {
                nrscc++;
                DFS_SCC(node, viz, scc, nrscc);
            }
        }
        cout << nrscc << "\n";
        for (int i = 1; i <= nrscc; i++)
        {
            for (int j : scc[i])
                cout << j << " ";
            cout << "\n";
        }

    }

};

vector <int> viz(dim);
stack <int> st;
stack <int> sol;
Graph <int> G;


void Solve_SortTop()
{
    ifstream fin ("sortaret.in");
    ofstream fout ("sortaret.out");
    int n , m;
    fin >> n >> m;
    G.Make_Graph(n , m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G.Add_edge(x, y);
    }
    sol = G.SortTop(viz, st);
    while (!sol.empty())
    {
        fout << sol.top() << " ";
        sol.pop();
    }
}


void Solve_SCC()
{
    ifstream fin ("ctc.in");
    ofstream fout ("ctc.out");
    int n, m;
    fin >> n >> m;
    G.Make_Graph(n, m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G.Add_edge(x, y);
        G.Add_reverse_edge(x, y);
    }
    G.SCC(viz, st);
}

int main()
{
    Solve_SCC();
    return 0;
}