Pagini recente » Cod sursa (job #2948606) | Cod sursa (job #237920) | Cod sursa (job #839217) | Cod sursa (job #421157) | Cod sursa (job #2866828)
#include <fstream>
#include <list>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N, viz[100100], viz2[100100];
list <int> parg;
vector <int> sol, G[100100], G_inv[100100];
vector <vector <int> > ctc;
void mark(int nod);
void dfs(int nod);
int main()
{
int M,x,y;
cin>>N>>M;
for(int i=1; i<=M; ++i)
{
cin>>x>>y;
G[x].pb(y);
G_inv[y].pb(x);
}
for(int i=1; i<=N; ++i)
if(!viz[i])
{
viz[i]=1;
dfs(i);
}
int nod;
while(!parg.empty())
{
nod=parg.back(); parg.pop_back();
if(!viz2[nod])
{
mark(nod);
ctc.pb(sol);
sol.clear();
}
}
cout<<ctc.size()<<'\n';
for(auto V:ctc){
sort(V.begin(),V.end());
for(auto it:V)
cout<<it<<' ';
cout<<'\n';
}
return 0;
}
void mark(int nod)
{
viz2[nod]=ctc.size()+1;
sol.pb(nod);
for(auto nn:G_inv[nod])
if(!viz2[nn])
mark(nn);
}
void dfs(int nod)
{
for(auto nn: G[nod])
if(!viz[nn]){
viz[nn]=1;
dfs(nn);
}
parg.pb(nod);
}