Pagini recente » Cod sursa (job #998905) | Cod sursa (job #236697) | Cod sursa (job #447391) | Cod sursa (job #550601) | Cod sursa (job #2759193)
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <vector>
#define IN_FILENAME "ctc.in"
#define OUT_FILENAME "ctc.out"
#define MAXV 100000
std::vector <int> G[MAXV + 1];
std::vector <int> Gt[MAXV + 1];
bool visited[MAXV + 1];
std::stack <int> topological_sort;
std::vector <std::vector <int>> sol;
std::vector <int> partial_sol;
void dfs(int node) {
for (int i = 0; i < G[node].size(); i++) {
int vec = G[node][i];
if (!visited[vec]) {
visited[vec] = true;
dfs(vec);
}
}
topological_sort.push(node);
}
void kosaraju(int node) {
for (int i = 0; i < Gt[node].size(); i++) {
int vec = Gt[node][i];
if (!visited[vec]) {
visited[vec] = true;
partial_sol.push_back(vec);
kosaraju(vec);
}
}
}
int main() {
int V, E;
std::ifstream input(IN_FILENAME);
input >> V >> E;
for (int i = 0; i < E; i++) {
int x, y;
input >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
visited[i] = true;
dfs(i);
}
}
memset(visited, 0, MAXV + 1);
while (!topological_sort.empty()) {
int curr = topological_sort.top();
topological_sort.pop();
if (!visited[curr]) {
partial_sol.clear();
visited[curr] = true;
partial_sol.push_back(curr);
kosaraju(curr);
sol.push_back(partial_sol);
}
}
std::ofstream output(OUT_FILENAME);
output << sol.size() << "\n";
for (auto &comp : sol) {
for (auto &node : comp) {
output << node << " ";
}
output << "\n";
}
}