Pagini recente » Cod sursa (job #1278433) | Cod sursa (job #1294163) | Cod sursa (job #3243148)
#include <fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<vector<int>> graph;
vector<int> visited;
void dfs(int u, vector<vector<int>>& graph, vector<int>& vout) {
visited[u] = true;
for (auto v : graph[u]) {
if (!visited[v]) {
dfs(v, graph, vout);
}
}
vout.push_back(u);
}
vector<vector<int>> getSCC(int n, int m, vector<vector<int>> graph) {
vector<int> vout;
visited = vector<int>(n + 1, false);
int u, v;
for (u = 0; u < n; u++) {
if (!visited[u]) {
dfs(u, graph, vout);
}
}
vector<vector<int>> rgraph= vector<vector<int>>(n+1);
for (v = 0; v < n; v++) {
for (auto u : graph[v]) {
rgraph[u].push_back(v);
}
}
visited = vector<int>(n + 1, false);
vector<vector<int>> components;
for (auto it = vout.rbegin(); it != vout.rend(); it++) {
if (!visited[*it]) {
vector<int> vcomp;
vector<int> vout2;
dfs(*it, rgraph, vout2);
sort(vout2.begin(), vout2.end());
components.push_back(vout2);
}
}
return components;
}
int main()
{
int i, j, n, m,u,v;
cin >> n >> m;
graph = vector<vector<int>>(n);
for (i = 0; i < m; i++) {
cin >> u >> v;
u--;
v--;
graph[u].push_back(v);
}
auto res = getSCC(n, m, graph);
cout << res.size() << "\n";
for (auto v : res) {
for (auto nr : v) {
cout << nr+1 << " ";
}
cout << "\n";
}
return 0;
}