Pagini recente » Cod sursa (job #2471371) | Cod sursa (job #1954174) | Cod sursa (job #1184508) | Cod sursa (job #296094) | Cod sursa (job #2896795)
#include <bits/stdc++.h>
#define INF ((int)1e9)
#define NMAX ((int)1e5)
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<int> adj[NMAX + 1];
vector<vector<int>> all_sccs;
void dfs(int node, vector<int> &parent, int ×tamp, vector<int> &found,
vector<int> &low_link, unordered_set<int> &nodes_set, stack<int> &nodes_stack) {
found[node] = ++timestamp;
low_link[node] = found[node];
nodes_set.insert(node);
nodes_stack.push(node);
for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
int next_node = *it;
if (parent[next_node] != -1) {
if (nodes_set.find(next_node) != nodes_set.end()) {
low_link[node] = min(low_link[node], found[next_node]);
}
continue;
}
parent[next_node] = node;
dfs(next_node, parent, timestamp, found, low_link, nodes_set, nodes_stack);
low_link[node] = min(low_link[node], low_link[next_node]);
}
if (low_link[node] == found[node]) {
vector<int> new_scc;
int x;
do {
x = nodes_stack.top();
nodes_stack.pop();
nodes_set.erase(x);
new_scc.push_back(x);
} while (x != node);
all_sccs.push_back(new_scc);
}
}
void tarjan_scc(vector<int> &parent, vector<int> &found, vector<int> &low_link) {
for (int i = 0; i <= n; ++i) {
parent[i] = -1;
found[i] = INF;
low_link[i] = INF;
}
unordered_set<int> nodes_set;
stack<int> nodes_stack;
int timestamp = 0;
for (int i = 1; i <= n; ++i) {
if (parent[i] == -1) {
parent[i] = i;
dfs(i, parent, timestamp, found, low_link, nodes_set, nodes_stack);
}
}
}
int main(void) {
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int src, dest;
fin >> src >> dest;
adj[src].push_back(dest);
}
vector<int> parent(n + 1);
vector<int> found(n + 1);
vector<int> low_link(n + 1);
tarjan_scc(parent, found, low_link);
fout << all_sccs.size() << "\n";
for (size_t i = 0; i < all_sccs.size(); ++i) {
for (size_t j = 0; j < all_sccs[i].size(); ++j) {
fout << all_sccs[i][j] << " ";
}
fout << "\n";
}
return 0;
}