Pagini recente » Cod sursa (job #752154) | Cod sursa (job #1243012) | Cod sursa (job #1783692) | Cod sursa (job #2096021) | Cod sursa (job #2789444)
#include <fstream>
#include <vector>
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
const int N = 1e5+1;
std::vector<int> g1[N], g2[N], ctc[N];
int n, m, sortTop[N], cnt, nrCtc;
bool vis[N];
void dfs(int i){
vis[i] = 1;
for(auto node : g1[i]){
if(vis[node]) continue;
dfs(node);
}
sortTop[cnt++] = i;
}
void reset_vis(){
for(int i=1;i<=n;++i){
vis[i] = 0;
}
}
void parcurgere(int i){
vis[i] = 1;
for(auto node : g2[i]){
if(vis[node]) continue;
parcurgere(node);
}
ctc[nrCtc].push_back(i);
}
int main(){
in>>n>>m;
for(int i=0;i<m;++i){
int a,b;
in>>a>>b;
g1[a].push_back(b);
g2[b].push_back(a);
}
for(int i=1;i<=n;++i){
if(vis[i]) continue;
dfs(i);
}
reset_vis();
for(int i=cnt-1;i>=0;--i){
if(vis[sortTop[i]]) continue;
parcurgere(sortTop[i]);
++nrCtc;
}
out<<nrCtc<<'\n';
for(int i=0;i<nrCtc;++i){
for(auto node : ctc[i]){
out<<node<<' ';
}
out<<'\n';
}
in.close();
out.close();
return 0;
}