Pagini recente » Cod sursa (job #2380538) | Cod sursa (job #2536783) | Cod sursa (job #1832447) | Cod sursa (job #612788) | Cod sursa (job #2928707)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
int onStack[100001], ids[100001], low[100001], idx;
stack <int> S;
vector <int> G[100001];
vector <vector <int>> Ans;
void strongConnect(int curent) {
ids[curent] = idx;
low[curent] = idx;
idx++;
S.push(curent);
onStack[curent] = 1;
for (int node : G[curent]) {
if (ids[node] == 0) {
strongConnect(node);
low[curent] = min(low[curent], low[node]);
}
else if (onStack[node]) {
low[curent] = min(low[curent], ids[node]);
}
}
if (ids[curent] == low[curent]) {
vector <int> scc;
int node;
do {
node = S.top();
S.pop();
onStack[node] = 0;
scc.push_back(node);
} while (curent != node);
Ans.push_back(scc);
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
fin >> u >> v;
G[u].push_back(v);
}
idx = 1;
for (int i = 1; i <= n; i++) {
if (ids[i] == 0) {
strongConnect(i);
}
}
fout << Ans.size() << "\n";
for (int i = 0; i < Ans.size(); i++) {
for (int j = 0; j < Ans[i].size(); j++) {
fout << Ans[i][j] << " ";
}
fout << "\n";
}
return 0;
}