Pagini recente » Cod sursa (job #2943661) | Cod sursa (job #290387) | Cod sursa (job #1078330) | Cod sursa (job #3002212) | Cod sursa (job #2372850)
#include <fstream>
#include <vector>
#include <stack>
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");
class Graph {
private:
int V;
std::vector<int>* table;
std::vector<int>* reverseTable;
private:
void DFS(int vertex, std::vector<bool>&visited, std::stack<int>&Stack) {
visited[vertex] = true;
std::vector<int>::iterator itEnd = table[vertex].end();
for (std::vector<int>::iterator it = table[vertex].begin(); it != itEnd; ++it) {
if (!visited[*it])
DFS(*it, visited, Stack);
}
Stack.push(vertex);
}
void reverseDFS(int vertex, std::vector<bool>&visited, std::vector<int>&component) {
visited[vertex] = false;
component.push_back(vertex);
std::vector<int>::iterator itEnd = reverseTable[vertex].end();
for (std::vector<int>::iterator it = reverseTable[vertex].begin(); it != itEnd; ++it) {
if (visited[*it])
reverseDFS(*it, visited, component);
}
}
public:
Graph(int numberOfVertices) {
V = numberOfVertices + 1;
table = new std::vector<int>[V];
reverseTable = new std::vector<int>[V];
}
void addEdge(int x, int y) {
table[x].push_back(y);
reverseTable[y].push_back(x);
}
void SCC() {
std::stack<int> Stack;
std::vector<bool> visited(V, false);
for (int i = 1; i < V; ++i)
if (!visited[i])
DFS(i, visited, Stack);
std::vector<std::vector<int>> components;
while (!Stack.empty()) {
int vertex = Stack.top();
Stack.pop();
if (visited[vertex]) {
std::vector<int> component;
reverseDFS(vertex, visited, component);
components.push_back(component);
}
}
int nrC = components.size();
g << nrC << '\n';
for (int i = 0; i < nrC; ++i) {
for (std::vector<int>::iterator it = components[i].begin(); it != components[i].end(); ++it) {
g << *it << " ";
}
g << '\n';
}
}
};
int main() {
int n;
f >> n;
Graph *myGraph = new Graph(n);
int m;
f >> m;
int x, y;
for (int i = 1; i <= m; ++i) {
f >> x >> y;
myGraph->addEdge(x, y);
}
myGraph->SCC();
return 0;
}