Cod sursa(job #2798114)

Utilizator Angel2IonitaAngel Ionita Angel2Ionita Data 10 noiembrie 2021 22:09:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <vector>
#include <fstream>
#include <stack>
#include <queue>
#include <iostream>

using namespace std;

ifstream f("ctc.in");
ofstream o("ctc.out");

class Graph
{
public:
    vector<vector<int>> adjList;
    int size;
    Graph(int n)
    {
        size = n;
        adjList.resize(size);
    }
    void addEdge(int start, int end)
    {
        adjList[start].push_back(end);
    }
    void DFS1(int node, vector<bool>& vis, stack<int>& S)
    {
        vis[node] = true;
        for (auto i : adjList[node])
            if (!vis[i])
                DFS1(i, vis, S);
        S.push(node);
    }
    void DFS2(int node, vector<bool>& vis)
    {
        vis[node] = true;
        o << node + 1 << " ";
        for (auto i : adjList[node])
            if (!vis[i])
                DFS2(i, vis);
    }
    Graph TransposeGraph()
    {
        Graph Tg(size);
        for (int i = 0; i < size; i++)
            for (auto j: adjList[i])
                Tg.adjList[j].push_back(i);
        return Tg;
    }
    void SCC()
    {
        stack<int> S;
        vector<bool> vis;
        for (int i = 0; i < size; i++)
            vis.push_back(false);
        for (int i = 0; i < size; i++)
            if (!vis[i])
                DFS1(i, vis, S);
        Graph Tg = TransposeGraph();
        for (int i = 0; i < size; i++)
            vis[i] = false;
        while (!S.empty())
        {
            int node = S.top();
            S.pop();
            if (!vis[node])
            {
                Tg.DFS2(node, vis);
                o << endl;
            }
        }
    }
};

int main()
{

    int n, m;
    int x, y;
    f >> n >> m;
    Graph g(n);
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        g.addEdge(x - 1, y - 1);
    }
    g.SCC();

    return 0;
}