Pagini recente » Cod sursa (job #3247996) | Cod sursa (job #2799075) | Cod sursa (job #391462) | Cod sursa (job #1340026) | Cod sursa (job #2814150)
#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;
}