Cod sursa(job #2925852)

Utilizator VladWero08Olaeriu Vlad Mihai VladWero08 Data 16 octombrie 2022 11:41:02
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M;
vector <vector<int> > AdjacencyList, AdjacencyListT, AllCTC;
stack <int> nodeOrder;
vector <bool> visited;

void DFS(int Node, vector<vector<int> > list){
    visited[Node] = true;

    for(int i = 0; i < list[Node].size(); i++){
        int NodeNext = list[Node][i];
        if(!visited[NodeNext])
            DFS(NodeNext,list);
    }

    nodeOrder.push(Node);
}

void DFST(int Node, vector<vector<int> > list, vector<int>&CTC){
    CTC.push_back(Node);
    visited[Node] = true;

    for(int i = 0; i < list[Node].size(); i++){
        int NodeNext = list[Node][i];
        if(!visited[NodeNext])
            DFST(NodeNext,list, CTC);
    }
}

int main() {
    fin >> N >> M;
    cout << N << M;
    for(int i = 0; i <= N; i++){
        AdjacencyList.push_back(vector<int>());
        AdjacencyListT.push_back(vector<int>());
        visited.push_back(false);
    }

    for(int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
        AdjacencyList[x].push_back(y);
        AdjacencyListT[y].push_back(x);
    }

    // Use DFS to create the stack that contains the nodes
    // in the order of how fast they've been finalized by the DFS
    for(int i = 1; i < AdjacencyList.size(); i++)
        if(!visited[i])
            DFS(i,AdjacencyList);

    // Reset the visited vector
    for(int i = 0; i < visited.size(); i++)
        visited[i] = false;

    // Traverse each node of the stack and apply DFS
    // - all the nodes reached from that search create a strongly connected component
    // - display it
    int NodeCurrent;

    while(!nodeOrder.empty()){
        NodeCurrent = nodeOrder.top();
        nodeOrder.pop();

        if(!visited[NodeCurrent]){
            vector <int> CTC;
            DFST(NodeCurrent, AdjacencyListT, CTC);
            AllCTC.push_back(CTC);
        }
    }

    fout << AllCTC.size() << endl;
    for( int i = 0; i < AllCTC.size(); i++){
        for(int j = 0; j < AllCTC[i].size(); j++)
            fout << AllCTC[i][j] << " ";
        fout << endl;
    }

    fin.close();
    fout.close();
    return 0;
}