Pagini recente » Cod sursa (job #928543) | Cod sursa (job #2651647)
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int viz[100100],viz2[100100],n;
vector <int> sol, G[100100], G_inv[100100], List;
vector < vector <int> > ctc;
void dfs(int nod)
{
viz[nod]=1;
for(auto nn:G[nod])
if(!viz[nn])
dfs(nn);
List.pb(nod);
}
void mark(int nod)
{
viz2[nod]=ctc.size()+1;
sol.pb(nod);
for(auto nn:G_inv[nod])
if(!viz2[nn])
mark(nn);
}
int main()
{
int m,x,y,el,k=0;
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])
{
++k;
dfs(i);
}
while(!List.empty())
{
el=List.back();
if(!viz2[el])
{
mark(el);
ctc.pb(sol);
sol.clear();
}
List.pop_back();
}
cout<<ctc.size()<<'\n';
for(auto it:ctc)
{
for(auto it1:it)
cout<<it1<<' ';
cout<<'\n';
}
return 0;
}