Pagini recente » Cod sursa (job #3305218) | Cod sursa (job #3343381) | Cod sursa (job #3319446) | Cod sursa (job #1690402) | Cod sursa (job #3343924)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, a, b;
int vaz[100005];
vector<int> ad[100005], ad2[100005], v;
vector<vector<int>> sol;
void topoSort(int nod){
vaz[nod]=1;
for(auto vecin: ad[nod]){
if(!vaz[vecin])
topoSort(vecin);
}
v.push_back(nod);
}
void dfs(int nod){
vaz[nod]=1;
sol[sol.size()-1].push_back(nod);
for(int vecin: ad2[nod]){
if(!vaz[vecin])
dfs(vecin);
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>a>>b;
ad[a].push_back(b);
ad2[b].push_back(a);
}
for(i=1;i<=n;i++){
if(!vaz[i])
topoSort(i);
}
for(i=1;i<=n;i++){
vaz[i]=0;
}
for(i=v.size()-1;i>=0;i--){
int nod=v[i];
if(!vaz[nod]){
sol.push_back(vector<int> {});
dfs(nod);
}
}
fout<<sol.size()<<'\n';
for(i=0;i<sol.size();i++){
for(auto nod: sol[i]){
fout<<nod<<" ";
}
fout<<'\n';
}
return 0;
}