Pagini recente » Cod sursa (job #2343785) | Cod sursa (job #3269579) | Cod sursa (job #2441082) | Cod sursa (job #1528911) | Cod sursa (job #3233960)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <unordered_set>
#define NMAX 100000
std::ifstream fin;
std::ofstream fout;
void dfs_top(int node, std::vector<int> adj[], std::unordered_set<int> &used, std::stack<int> &st)
{
used.insert(node);
for (auto neigh : adj[node])
if (used.find(neigh) == used.end())
dfs_top(neigh, adj, used, st);
st.push(node);
}
void dfs_scc(int node, std::vector<int> adj[], std::unordered_set<int> &used, std::vector<int> &scc)
{
scc.push_back(node);
used.insert(node);
for (auto neigh : adj[node])
if (used.find(neigh) == used.end())
dfs_scc(neigh, adj, used, scc);
}
int main()
{
int n, m;
std::vector<int> adj[NMAX], adjt[NMAX];
std::unordered_set<int> used;
std::stack<int> top_sort;
std::vector<std::vector<int>> sccs;
fin.open("ctc.in");
fout.open("ctc.out");
fin >> n >> m;
for (int src, dest, i = 0; i < m; ++i) {
fin >> src >> dest;
adj[src - 1].push_back(dest - 1);
adjt[dest - 1].push_back(src - 1);
}
for (int v = 0; v < n; ++v)
if (used.find(v) == used.end())
dfs_top(v, adj, used, top_sort);
used.clear();
while (!top_sort.empty()) {
auto v = top_sort.top();
top_sort.pop();
if (used.find(v) == used.end()) {
sccs.push_back({});
dfs_scc(v, adjt, used, sccs.back());
}
}
fout << sccs.size() << '\n';
for (auto &scc : sccs) {
for (auto node : scc)
fout << node + 1 << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}