Pagini recente » Cod sursa (job #1883853) | Cod sursa (job #1850617) | Istoria paginii runda/22_februarie_simulare_oji_2024_clasa_9 | Istoria paginii utilizator/rania.butuc | Cod sursa (job #3187110)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>V[100002];
vector<int>Vt[100002];
vector<int> Componente[100002];
stack<int>S;
int n,m,ctc,v[100002];
void dfs(int k){
v[k]=1;
for(auto vec:V[k])
if(!v[vec]) dfs(vec);
S.push(k);
}
void dfs2(int k){
v[k]=2;
Componente[ctc].push_back(k);
for(auto vec:Vt[k])
if(v[vec]==1) dfs2(vec);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;++i){
int a,b;
cin>>a>>b;
V[a].push_back(b);
Vt[b].push_back(a);
}
//topo sort
for(int i=1;i<=n;++i)
if(!v[i]) dfs(i);
while(!S.empty()){
int nod=S.top();
S.pop();
if(v[nod]==1){
ctc++;
dfs2(nod);
}
}
cout<<ctc<<'\n';
for(int i=1;i<=ctc;++i,cout<<'\n')
for(int j=0;j<Componente[i].size();++j) cout<<Componente[i][j]<<" ";
return 0;
}