Cod sursa(job #2926694)

Utilizator VladWero08Olaeriu Vlad Mihai VladWero08 Data 18 octombrie 2022 13:54:05
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 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;
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, string &CTC){
    CTC = CTC + to_string(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;

    AdjacencyList.resize(N+1);
    AdjacencyListT.resize(N+1);
    visited.resize(N+1);

    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
    visited.assign(visited.size(),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;
    vector <string> CTC;

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

        if(!visited[NodeCurrent]){
            string empty;
            DFST(NodeCurrent, AdjacencyListT, empty);
            CTC.push_back(empty);
        }
    }

    fout << CTC.size() << endl;
    for(int i = 0; i < CTC.size(); i++)
        fout << CTC[i] << endl;

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