Pagini recente » Cod sursa (job #3164652) | Cod sursa (job #3210924) | Cod sursa (job #409102) | Cod sursa (job #3159824) | Cod sursa (job #3229155)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax = 1e5+10;
int n,m,numar;
vector<vector<int>> mat1(nmax),mat2(nmax),ans(nmax);
vector<int> visited(nmax),noduri;
void read_input(){
fin >> n >> m;
int nod_1,nod_2;
for(int i = 1;i <=m; i++){
fin >> nod_1 >> nod_2;
mat1[nod_1].push_back(nod_2);
mat2[nod_2].push_back(nod_1);
}
};
void dfs1(int nod){
visited[nod] = 1;
for(auto nod_aux : mat1[nod]){
if(!visited[nod_aux]){
dfs1(nod_aux);
}
};
noduri.push_back(nod);
};
void solve1(){
for(int i = 1; i <=n; i++){
if(!visited[i]){
dfs1(i);
}
}
};
void dfs2(int nod,int numar){
visited[nod] = 1;
for(auto nod_aux : mat2[nod]){
if(!visited[nod_aux]){
ans[numar].push_back(nod_aux);
dfs2(nod_aux,numar);
}
}
};
void solve2(){
reverse(noduri.begin(),noduri.end());
fill(visited.begin(),visited.end(),0);
numar = 0;
for(auto i : noduri){
if(!visited[i]){
numar++;
ans[numar].push_back(i);
dfs2(i,numar);
}
};
fout << numar << '\n';
for(int i = 1; i <=numar; i++,fout << '\n'){
sort(ans[i].begin(),ans[i].end());
for(auto x : ans[i]){
fout << x << " ";
}
}
}
int main(){
read_input();
solve1();
solve2();
return 0;
}