Pagini recente » Cod sursa (job #1068812) | Cod sursa (job #258285) | Cod sursa (job #1918438) | Cod sursa (job #950691) | Cod sursa (job #2955333)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, q;
vector<int> g[100001], gt[100001], a[100001];
stack<int> s;
int v[100001]; // visited
void read() {
int x, y;
cin >> n >> m;
while (m--) {
cin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
void show() {
for (int i = 1; i <= n; i++) {
cout << "i: " << i << ": ";
for (int j = 0; j < g[i].size(); j++) {
cout << g[i][j] << ' ';
}
cout << '\n';
}
}
void show2() {
for (int i = 1; i <= n; i++) {
for (int j = 0; j < gt[i].size(); j++) {
cout << gt[i][j] << ' ';
}
}
}
void dfs(int x) {
v[x] = 1;
for (int i = 0; i < g[x].size(); i++) {
if (v[g[x][i]] == 0) {
dfs(g[x][i]);
}
}
s.push(x);
}
void dfs2(int x) {
v[x] = 2;
a[q].push_back(x);
for (int i = 0; i < gt[x].size(); i++) {
if (v[gt[x][i]] == 1) {
dfs2(gt[x][i]);
}
}
}
int main() {
read();
for (int i = 1; i < n; i++) {
if (v[i] == 0) {
dfs(i);
}
}
while (!s.empty()) {
if (v[s.top()] == 1) {
dfs2(s.top());
q++;
}
else {
s.pop();
}
}
cout << q << '\n';
for (int i = 0; i < q; i++) {
for (int j = 0; j < a[i].size(); j++) {
cout << a[i][j] << ' ';
}
cout << '\n';
}
return 0;
}