Pagini recente » Rating cont de incercari (Albert_Andrei) | Cod sursa (job #357721) | Cod sursa (job #1637083) | Cod sursa (job #2961348) | Cod sursa (job #3243146)
#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, stack<int>& sout) {
visited[u] = true;
for (auto v : graph[u]) {
if (!visited[v]) {
dfs(v, graph, sout);
}
}
sout.push(u);
}
vector<vector<int>> getSCC(int n, int m, vector<vector<int>> graph) {
stack<int> sout;
visited = vector<int>(n + 1, false);
int u, v;
for (u = 0; u < n; u++) {
if (!visited[u]) {
dfs(u, graph, sout);
}
}
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 (u = 0; u < n; u++) {
if (!visited[u]) {
vector<int> vcomp;
sout = stack<int>();
dfs(u, rgraph, sout);
while (!sout.empty()) {
vcomp.push_back(sout.top()+1);
sout.pop();
}
sort(vcomp.begin(), vcomp.end());
components.push_back(vcomp);
}
}
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 << " ";
}
cout << "\n";
}
return 0;
}