Pagini recente » Cod sursa (job #1034538) | Cod sursa (job #1793342) | Cod sursa (job #178398) | Cod sursa (job #821647) | Cod sursa (job #3296503)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5;
vt <int> adj[NMAX + 1];
vt <int> adj_r[NMAX + 1];
bool viz[NMAX + 1];
vt <int> topo;
void dfs1(int node){
viz[node] = 1;
for(int vec : adj[node]){
if(!viz[vec]){
dfs1(vec);
}
}
topo.pb(node);
}
vt <vt <int>> comps;
vt <int> aux;
void dfs2(int node){
aux.pb(node);
viz[node] = 1;
for(int vec : adj_r[node]){
if(!viz[vec]){
dfs2(vec);
}
}
}
int main(){
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b;
fin >> a >> b;
adj[a].pb(b);
adj_r[b].pb(a);
}
for(int i = 1; i <= n; i++){
if(!viz[i]){
dfs1(i);
}
}
reverse(all(topo));
for(int i = 1; i <= n; i++){
viz[i] = 0;
}
for(int x : topo){
if(!viz[i]){
aux.clear();
dfs2(i);
comps.pb(aux);
}
}
fout << sz(comps) << '\n';
for(vt <int> comp : comps){
for(int x : comp){
fout << x << ' ';
}
fout << '\n';
}
return 0;
}