Cod sursa(job #2758647)

Utilizator lahayonTester lahayon Data 11 iunie 2021 20:05:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <stack>


using namespace std;


// Tarjan

void dfs(int node, int& index, vector<int>& idx, vector<int>& lowlink, vector<bool>& instack, stack<int>& DFS,  const vector<vector<int>>& graph, vector<vector<int>>& components){


    idx[node] = lowlink[node] = ++index;
    DFS.push(node);
    instack[node] = true;
    
    for(auto adjacent : graph[node]){
        if(idx[adjacent] == -1){
            dfs(adjacent, index, idx, lowlink, instack, DFS, graph, components);
            lowlink[node] = min(lowlink[node], lowlink[adjacent]);
        }
        else if(instack[adjacent]){
            lowlink[node] = min(lowlink[node], lowlink[adjacent]);
        }
    }
    if(idx[node] == lowlink[node]){
        components.push_back({});
        int current;
        do{
            current = DFS.top();
            components[components.size() - 1].push_back(current);
            instack[current] = false;
            DFS.pop();
        }while(current != node);
    }
}


int main()
{
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
         

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph;
    vector<int> idx, lowlink;
    vector<bool> instack;
    for(int i = 0; i < N; ++i){
        graph.push_back({});
        idx.push_back(-1);
        lowlink.push_back(-1);
        instack.push_back(false);
    }

    for(int x, y; M > 0; --M){

        cin >> x >> y;
        --x; --y;
        graph[x].push_back(y);
    }

    vector<vector<int>> components;
    int index = 0;

    for(int i = 0; i < N; ++i)
        if(idx[i] == -1){
              stack<int> DFS;
              dfs(i, index, idx, lowlink, instack, DFS, graph, components);
        }
        
   
    cout << components.size() << "\n";
    for(auto component : components){
        for(auto component_member : component)
            cout << component_member + 1 << " ";

        cout << "\n";
    }



    cin.close();
    cout.close();

    return 0;
}