Pagini recente » Cod sursa (job #137154) | Cod sursa (job #2038042) | Cod sursa (job #1786414) | Cod sursa (job #2560921) | Cod sursa (job #2205987)
#include <fstream>
#include <stack>
#include <vector>
int main() {
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
int n, m;
in >> n >> m;
std::vector<std::vector<int>> graph;
std::vector<std::vector<int>> tgraph;
std::vector<bool> visited;
graph.reserve(n);
tgraph.reserve(n);
visited.reserve(n);
for (int i = 0; i < n; i++) {
graph.push_back(std::vector<int>());
tgraph.push_back(std::vector<int>());
visited.push_back(false);
}
for (int i = 0; i < m; i++) {
int from, to;
in >> from >> to;
graph[from - 1].push_back(to);
tgraph[to - 1].push_back(from);
}
std::stack<int> vertices;
for (int i = 1; i <= n; i++) {
if (!visited[i - 1]) {
visited[i - 1] = true;
std::stack<int> s;
s.push(i);
while (!s.empty()) {
int u = s.top();
bool hasAnyNeighbors = false;
for (int v : graph[u - 1]) {
if (!visited[v - 1]) {
visited[v - 1] = true;
s.push(v);
hasAnyNeighbors = true;
break;
}
}
if (!hasAnyNeighbors) {
vertices.push(u);
s.pop();
}
}
}
}
std::vector<std::vector<int>> sC;
for (int i = 0; i < n; i++) visited[i] = false;
while (!vertices.empty()) {
int curr = vertices.top();
vertices.pop();
if (!visited[curr - 1]) {
sC.push_back(std::vector<int>());
visited[curr - 1] = true;
std::stack<int> s;
s.push(curr);
sC[sC.size() - 1].push_back(curr);
while (!s.empty()) {
int u = s.top();
bool hasAnyNeighbors = false;
for (int v : tgraph[u - 1]) {
if (!visited[v - 1]) {
visited[v - 1] = true;
s.push(v);
sC[sC.size() - 1].push_back(v);
hasAnyNeighbors = true;
break;
}
}
if (!hasAnyNeighbors) s.pop();
}
}
}
out << sC.size() << "\n";
for (auto c : sC) {
for (int u : c) {
out << u << " ";
}
out << "\n";
}
return 0;
}