Pagini recente » Cod sursa (job #2400935) | Cod sursa (job #1077719) | Cod sursa (job #1430337) | Cod sursa (job #1226439) | Cod sursa (job #3004784)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define pb push_back
#define ll long long
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 1e5 + 5;
const char nl = '\n';
int n, m, f[NMAX], len;
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[a].pb(b);
}
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;
}