Cod sursa(job #2814150)

Utilizator atudoreimirunaAtudorei Miruna Gabriela atudoreimiruna Data 7 decembrie 2021 17:35:30
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define Max 100005

using namespace std;

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

int N, M;

vector<int> strongly_connected_components[Max];
bool visitedDFS[Max], visitedDFStranspose[Max];   // pentru DFS pe grafurile initial si transpus
vector<int> transpose_graph[Max];
// stiva pentru memorarea nodurilor in ordinea timpilor de final
int Stack[Max], top;

class Graph{
private:
    int NumberOfNodes, NumberOfEdges;
    vector<int> adjacencyList[Max];

public:
    Graph(int N, int M); // constructor
    void Read_Directed_Transpose_Graph();
    void DFS_initial_graph(int node);    // graful initial
    void DFS_transpose_graph(int node, int ct);
    void StronglyConnectedComponents();
    void Transpose_Graph();
    void Crossing();
};

// constructor
Graph :: Graph(int N, int M)
{
    NumberOfNodes = N;
    NumberOfEdges = M;
    // matrice_adiacenta = matrice;
}

void Graph :: Read_Directed_Transpose_Graph()
{
    for ( int i = 1; i <= NumberOfEdges; i++ )
    {
        int x, y;
        fin >> x >> y;
        adjacencyList[x].push_back(y);
        transpose_graph[y].push_back(x);
    }
}

void Graph :: DFS_initial_graph(int node)
{
    visitedDFS[node] = 1;

    for ( auto i : adjacencyList[node] )
        if ( !visitedDFS[i] )
            DFS_initial_graph(i);

    // pentru nodul x putem stabili timpul de finalizare si il memoram in stiva
    Stack[++top] = node;    
}

void Graph :: DFS_transpose_graph(int node, int ct)
{
    visitedDFStranspose[node] = 1;
    strongly_connected_components[ct].push_back(node);

    for ( auto i : transpose_graph[node] )
        if ( !visitedDFS[i] )
            DFS_transpose_graph(i, ct);
}

// stabilim timpul de finalizare pentru fiecare nod
void Graph :: Crossing()   // cel initial
{
    for ( int i = 1; i <= NumberOfNodes; i++ )
        if ( ! visitedDFS[i] )
            DFS_initial_graph(i);
}

void Graph :: StronglyConnectedComponents()
{
    int ct_comp = 0;

    // cat timp exista elemente in stiva
    while( top )
    {
        // parcurgem in adancime graful transpus
        // consideram nodurile in ordinea descrescatoare timpilor de finalizare
        if( !visitedDFStranspose[Stack[top]] )
        {
            ct_comp ++;
            DFS_transpose_graph(Stack[top], ct_comp);  // DFS in graful transpus
        }
        top--;
    }
 
    fout << ct_comp << "\n";
 
    for ( int i = 1; i <= ct_comp; i++ )
    {
        for( auto j : strongly_connected_components[i] )
                fout << j << " ";
        fout << "\n";
    }
}

int main()
{
    fin >> N >> M;
    Graph G(N, M);
    G.Read_Directed_Transpose_Graph();
    G.Crossing();
    G.StronglyConnectedComponents();

    return 0;
}