Pagini recente » Cod sursa (job #2546395) | Cod sursa (job #945655) | Cod sursa (job #31081) | Cod sursa (job #1913684) | Cod sursa (job #3124210)
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100005];
int n, m;
int parent[100005];
int timestamp = 0;
int found[100005];
int low_link[100005];
stack<int> visiting_stack;
bool is_in_stack[100005];
vector<vector<int>> all_sccs;
vector<int> scc;
ifstream in("ctc.in");
ofstream out("ctc.out");
void DFS(int node) {
found[node] = ++timestamp;
low_link[node] = timestamp;
visiting_stack.push(node);
is_in_stack[node] = true;
for (auto neigh : adj[node]) {
if (parent[neigh] != 0) {
if (is_in_stack[neigh])
low_link[node] = min(low_link[node], low_link[neigh]);
} else {
parent[neigh] = node;
DFS(neigh);
low_link[node] = min(low_link[node], low_link[neigh]);
}
}
if (found[node] == low_link[node]) {
scc.clear();
int x;
do {
x = visiting_stack.top();
visiting_stack.pop();
is_in_stack[x] = false;
scc.push_back(x);
} while (x != node);
all_sccs.push_back(scc);
}
}
int main() {
in >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
in >> x >> y;
adj[x].push_back(y);
}
for (int i = 1; i <= n; i++)
low_link[i] = 1e9;
for (int i = 1; i <= n; i++) {
if (parent[i] == 0) {
parent[i] = i;
DFS(i);
}
}
out << all_sccs.size() << '\n';
for (auto scc : all_sccs) {
for (auto node : scc) {
out << node << ' ';
}
out << '\n';
}
}