Pagini recente » Cod sursa (job #2757908) | Cod sursa (job #3120716) | Cod sursa (job #145531) | Diferente pentru implica-te/arhiva-educationala intre reviziile 221 si 222 | Cod sursa (job #2192877)
#include<iostream>
#include<vector>
#include<stack>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef unordered_map<int, vector<int> > graph;
void dfs_inner(graph &G, int node, unordered_set<int> &used, vector<int> &comp) {
used.insert(node);
comp.push_back(node);
for (const auto &child : G[node]) {
if (used.find(child) == used.end()) {
dfs_inner(G, child, used, comp);
}
}
}
vector<vector<int> > dfs(graph &G, const vector<int> &top_sort) {
unordered_set<int> used;
vector<vector<int> > ans;
for (const auto &node : top_sort) {
if (used.find(node) == used.end()) {
vector<int> comp;
dfs_inner(G, node, used, comp);
ans.push_back(comp);
}
}
return ans;
}
void topological_sort_inner(graph &G, int node, unordered_set<int> &used, stack<int> &st) {
used.insert(node);
for (const auto &child : G[node]) {
if (used.find(child) == used.end()) {
topological_sort_inner(G, child, used, st);
}
}
st.push(node);
}
vector<int> topological_sort(graph &G) {
unordered_set<int> used;
stack<int> st;
for (const auto &it : G) {
if (used.find(it.first) == used.end()) {
topological_sort_inner(G, it.first, used, st);
}
}
vector<int> ans;
while (!st.empty()) {
ans.push_back(st.top());
st.pop();
}
return ans;
}
graph transpose(graph &G) {
graph T;
for (const auto &it : G) {
for (const auto &child : G[it.first]) {
T[child].push_back(it.first);
}
}
return T;
}
vector<vector<int> > scc(graph &G) {
graph T = transpose(G);
vector<int> top_sort = topological_sort(G);
return dfs(T, top_sort);
}
int main () {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, x, y, i;
graph G;
cin >> n >> m;
for (i = 0; i < m; i++) {
cin >> x >> y;
G[x].push_back(y);
}
vector<vector<int> > components = scc(G);
cout << components.size() << endl;
for (const auto &comp : components) {
for (const auto &node : comp) {
cout << node << ' ';
}
cout << endl;
}
return 0;
}