Pagini recente » Cod sursa (job #1764019) | Cod sursa (job #587153) | Cod sursa (job #3247268) | Cod sursa (job #2022628) | Cod sursa (job #1960869)
#include <stdio.h>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
vector<vector<int> > edges, sol;
stack<int> ordered_vertices;
unordered_set<int> visited;
void secondDFS(int node) {
visited.insert(node);
sol.back().push_back(node);
for (auto it : edges[node]) {
if (visited.find(it) == visited.end()) {
secondDFS(it);
}
}
}
void reverseGraph() {
vector<vector<int> > reversed_graph;
vector<int> t;
for (int i = 0; i < edges.size(); i ++) {
reversed_graph.push_back(t);
}
for (int i = 1; i < edges.size(); i ++) {
for (int j = 0; j < edges[i].size(); j ++) {
reversed_graph[edges[i][j]].push_back(i);
}
}
edges = reversed_graph;
}
void firstDFS(int node) {
visited.insert(node);
for (auto it : edges[node]) {
if (visited.find(it) == visited.end()) {
firstDFS(it);
}
}
ordered_vertices.push(node);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("crc.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
vector<int> t;
for (int i = 0; i <= n; i ++) {
edges.push_back(t);
}
for (int i = 0; i < m; i ++) {
int a, b;
scanf("%d %d", &a, &b);
edges[a].push_back(b);
}
for (int i = 1; i <= n; i ++) {
if (visited.find(i) == visited.end()) {
firstDFS(i);
}
}
reverseGraph();
visited.clear();
while (!ordered_vertices.empty()) {
int node = ordered_vertices.top();
ordered_vertices.pop();
if (visited.find(node) == visited.end()) {
sol.push_back(t);
secondDFS(node);
}
}
printf("%d\n", sol.size());
for (int i = 0; i < sol.size(); i ++) {
for (int j = 0; j < sol[i].size(); j ++) {
printf("%d ", sol[i][j]);
}
printf("\n");
}
}