Pagini recente » Istoria paginii runda/9titus/clasament | Cod sursa (job #1009639) | Cod sursa (job #2102328) | Cod sursa (job #1229274) | Cod sursa (job #3029960)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100005;
const char nl = '\n';
int n, m, len, f[NMAX];
vector<int> v[NMAX], rev[NMAX], order, comp;
vector<vector<int>> ans;
void dfs(int node){
f[node] = 1;
for(auto neigh: v[node]){
if(!f[neigh])
dfs(neigh);
}
order.pb(node);
}
void kosaraju(int node){
f[node] = 1;
comp.pb(node);
for(auto neigh: rev[node]){
if(!f[neigh])
kosaraju(neigh);
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; ++i){
int a, b;
in >> a >> b;
v[a].pb(b);
rev[b].pb(a);
}
for(int i = 1; i <= n; ++i){
if(!f[i])
dfs(i);
}
reverse(order.begin(), order.end());
for(int i = 1; i <= n; ++i)
f[i] = 0;
for(auto i: order){
if(!f[i]){
len++;
kosaraju(i);
ans.pb(comp);
comp.clear();
}
}
out << len << nl;
for(auto i: ans){
for(auto j: i)
out << j << ' ';
out << nl;
}
return 0;
}