Pagini recente » Cod sursa (job #1422903) | Cod sursa (job #576627) | Cod sursa (job #3237911) | Cod sursa (job #141734) | Cod sursa (job #2878873)
#include <bits/stdc++.h>
using namespace std;
const long long NR = 1e6 + 25;
vector<vector<int>> v;
vector<int> highest, vis, curr, nodes;
int n, m, lvl = 1;
vector<vector<int>> scc;
void dfs(int nod) {
vis[nod] = lvl;
highest[nod] = lvl;
++lvl;
nodes.push_back(nod);
curr[nod] = 1;
for (auto it : v[nod]) {
if (!vis[it]) {
dfs(it);
highest[nod] = min(highest[nod], highest[it]);
} else {
if (curr[it]) {
highest[nod] = min(highest[nod], highest[it]);
}
}
}
if (vis[nod] == highest[nod]) {
vector<int> temp;
int node = -1;
while (node != nod) {
node = nodes.back();
curr[nodes.back()] = 0;
temp.emplace_back(nodes.back());
nodes.pop_back();
}
scc.emplace_back(temp);
}
}
ifstream in("ctc.in");
ofstream out("ctc.out");
signed main() {
int x, y;
in >> n >> m;
v.resize(n + 1, vector<int>());
highest.resize(n + 1, 0);
vis.resize(n + 1, 0);
curr.resize(n + 1, 0);
for (int i = 1; i <= m; ++i) {
in >> x >> y;
v[x].emplace_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
}
}
out << scc.size() << '\n';
for (auto it : scc) {
sort(it.begin(), it.end());
for (auto it2 : it) {
out << it2 << ' ';
}
out << '\n';
}
return 0;
}