Pagini recente » Cod sursa (job #2668530) | Cod sursa (job #1363537) | Cod sursa (job #1094887) | Cod sursa (job #354079) | Cod sursa (job #3005584)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y,k,nrc;
vector<vector<int> > G,GT;
vector<int> viz,vizt,timp,comp;
void dfs(int nod){
viz[nod]=1;
for(auto t:G[nod])
if(viz[t]==0)
dfs(t);
timp[++k]=nod;
}
void dfst(int nod){
vizt[nod]=1;
comp[nod]=nrc;
for(auto t:GT[nod])
if(vizt[t]==0)
dfst(t);
}
void rezolvare(){
for(int i=1;i<=n;++i)
if(viz[i]==0)
dfs(i);
for(int i=n;i>=1;--i)
if(vizt[timp[i]]==0)
nrc++,dfst(timp[i]);
}
int main()
{
fin>>n>>m;
G=GT=vector<vector<int> > (m+1);
viz=vizt=timp=comp=vector<int> (n+1);
for(int i=1;i<=m;++i){
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
rezolvare();
fout<<nrc<<'\n';
for(int i=1;i<=nrc;++i,fout<<'\n')
for(int j=1;j<=n;++j)
if(comp[j]==i)
fout<<j<<" ";
return 0;
}