Cod sursa(job #2927375)

Utilizator VladWero08Olaeriu Vlad Mihai VladWero08 Data 20 octombrie 2022 11:28:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

#define MAXN  100005

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

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

    for(it = list[Node].begin(); it != list[Node].end(); it++){
        if(!visited[*it])
            DFS(*it,list);
    }

    nodeOrder.push(Node);
}

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

    for(it = list[Node].begin(); it != list[Node].end(); it++){
        if(!visited[*it])
            DFST(*it,list, CTC);
    }
}

int main() {
    vector <int>::iterator it;
    fin >> N >> M;
    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 <= N; 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, NrCTC = 0;

    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(it = AllCTC[i].begin(); it != AllCTC[i].end(); it++)
            fout << *it << " ";
        fout << endl;
    }

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