Pagini recente » Cod sursa (job #2162894) | Cod sursa (job #1064139) | Cod sursa (job #1441963) | Borderou de evaluare (job #2107029) | Cod sursa (job #847408)
Cod sursa(job #847408)
#include<fstream>
#include<vector>
#define lim 100006
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[lim],T[lim],Solutie[lim];
int n,m,i,j,x,y,ctc,dim;
int viz[lim],Mark[lim],st[lim];
void DFP(int nod ) {
viz[nod]=1;
for(int i=0;i<G[nod].size();++i)
if(!viz[G[nod][i]])
DFP(G[nod][i]);
st[++dim]=nod;
}
void DFM(int nod,int ctc){
Mark[nod]=ctc;
for(int i=0;i<T[nod].size();++i)
if(!Mark[T[nod][i]])
DFM(T[nod][i],ctc);
}
int main (){
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
G[x].push_back(y);
T[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!viz[i])
DFP(i);
for(;dim;st[dim--]=0){
if(Mark[st[dim]]==0)
DFM(st[dim],++ctc);
}
for(i=1;i<=n;++i)
Solutie[Mark[i]].push_back(i);
g<<ctc<<"\n";
for(int i=1;i<=ctc;i++){
for(int j=0;j<Solutie[i].size();++j)
g<<Solutie[i][j]<<" ";
g<<"\n";
}
return 0;
}