Pagini recente » Cod sursa (job #1167198) | Cod sursa (job #1852418) | Cod sursa (job #2445024) | Cod sursa (job #1233060) | Cod sursa (job #1232392)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005
using namespace std;
bool viz[NMAX];
int timp[NMAX], nr;
vector<int> v[NMAX];
vector<int> v2[NMAX];
vector<int> p;
vector<int> sol[NMAX];
void DFS(int x, int t) {
++t;
viz[x] = 1;
int size = v[x].size();
for(int i = 0; i < size; ++i) {
if(!viz[v[x][i]]) {
DFS(v[x][i], t);
}
}
timp[x] = ++t;
}
bool cmp(int i, int j) {
return timp[i] > timp[j];
}
void DFS_inv(int x) {
viz[x] = 1;
p.push_back(x);
int size = v2[x].size();
for(int i = 0; i < size; ++i) {
if(!viz[v2[x][i]]) {
DFS_inv(v2[x][i]);
}
}
int sizep = p.size();
for(int i = 0; i < sizep; ++i)
sol[nr].push_back(p[i]);
p.clear();
}
int main ()
{
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, x, y;
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
cin >> x >> y;
v[x].push_back(y);
v2[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!viz[i]) {
DFS(i, 1);
}
for(int i = 1; i <= n; ++i)
viz[i] = 0;
for(int i = 1; i <= n; ++i)
sort(v2[i].begin(), v2[i].end(), cmp);
for(int i = 1; i <= n; ++i)
if(!viz[i]) {
++nr;
DFS_inv(i);
}
cout << nr << '\n';
for(int i = 1; i <= nr; ++i, cout << '\n')
for(int j = 0; j < sol[i].size(); ++j)
cout << sol[i][j] << ' ';
return 0;
}