Pagini recente » Cod sursa (job #1232392) | Cod sursa (job #1232215) | Cod sursa (job #2758826) | Cod sursa (job #2678021) | Cod sursa (job #1233070)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005
using namespace std;
bool viz[NMAX];
int timp[NMAX], nr, n, t, cur;
vector<int> v[NMAX];
vector<int> v2[NMAX];
vector<int> p;
vector<int> sol[NMAX];
void DFS(int x) {
viz[x] = 1;
int size = v[x].size();
for(int i = 0; i < size; ++i) {
if(!viz[v[x][i]]) {
DFS(v[x][i]);
}
}
timp[++t] = x;
}
bool cmp(int i, int j) {
return timp[i] > timp[j];
}
void DFS_inv(int x) {
viz[x] = 1;
p.push_back(x);
for(int i = 0; i < v2[x].size(); ++i) {
//cout << "vecin al lui " << x << ": " << v2[x][i] << '\n';
if(!viz[v2[x][i]]) {
DFS_inv(v2[x][i]);
}
}
}
int main ()
{
//ifstream cin("ctc.in");
//ofstream cout("ctc.out");
int 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);
}
for(int i = 1; i <= n; ++i)
viz[i] = 0;
for(int i = n; i >= 1; --i)
if(!viz[timp[i]]) {
DFS_inv(timp[i]);
int sizep = p.size();
if(sizep)
++nr;
for(int i = 0; i < sizep; ++i)
sol[nr].push_back(p[i]);
p.clear();
}
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;
}