Cod sursa(job #2569588)

Utilizator mirceatlxhaha haha mirceatlx Data 4 martie 2020 12:44:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb

#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#define MaxNumberOfNodes 100005
using namespace std;

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

vector <int> InitGraph[MaxNumberOfNodes], ReverseGraph[MaxNumberOfNodes];
vector <int> StrongComponents[MaxNumberOfNodes];
stack <int> Stack;
int N, M, strongComponents;
bool visited[MaxNumberOfNodes];

void FirstDFS(int node)
{
    int currentNode;
    visited[node] = true;
    for(int i = 0; i < InitGraph[node].size(); i++){
        currentNode = InitGraph[node][i];
        if(visited[currentNode] == false){
            FirstDFS(currentNode);
        }
    }
    Stack.push(node);
}

void SecondDFS(int node)
{
    int currentNode;
    visited[node] = true;
    StrongComponents[strongComponents].push_back(node);
    for(int i = 0; i < ReverseGraph[node].size(); i++){
        currentNode = ReverseGraph[node][i];
        if(!visited[currentNode]){
            SecondDFS(currentNode);
        }
    }
}

int main()
{
    int nodeX, nodeY, currentNode;
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> nodeX >> nodeY;
        InitGraph[nodeX].push_back(nodeY);
        ReverseGraph[nodeY].push_back(nodeX);
    }
    for(int i = 1; i <= N; i++){
        if(!visited[i]){
            FirstDFS(i);
        }
    }
    memset(visited,false,sizeof(visited));
    while(!Stack.empty()){
        currentNode = Stack.top();
        if(visited[currentNode] == false){
            ++strongComponents;
            SecondDFS(currentNode);
        }
        Stack.pop();
    }
    cout << strongComponents << "\n";
    for(int i = 1; i <= strongComponents; i++){
        for(int j = 0; j < StrongComponents[i].size(); j++){
            cout << StrongComponents[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}