Pagini recente » Istoria paginii runda/sim0001 | Cod sursa (job #2081091) | Profil analuca123 | Diferente pentru verkhoyansk/solutie_romana intre reviziile 4 si 6 | Cod sursa (job #2756490)
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream fin("ctc.in");
ifstream fout("ctc.out");
int A[100][100],x,postordine[100],viz[100],n,m,y,nr=0,nrm=0,vfs=0,vfMax=0,prag=0,AT[100][100];
//sortare topologica
void dfs (int x){
viz[x]=1;
//cout<<x<<" ";
for(int i=1;i<=A[x][0];i++)
if(viz[A[x][i]]==0){
dfs(A[x][i]);
}
postordine[++nr]=x;
}
void dfst (int x, int root){
viz[x]=0-root;
//cout<<x<<" ";
for(int i=1;i<=AT[x][0];i++)
if(viz[AT[x][i]]>0){
dfst(AT[x][i],root);
}
}
void dfst2 (int x){
viz[x]=1;
fout<<x<<" ";
for(int i=1;i<=AT[x][0];i++)
if(viz[AT[x][i]]<1){
dfst2(AT[x][i]);
}
}
int main()
{
fin>>n;
fin>>m;
for(int i=0;i<m;i++)
{
fin>>x>>y;
A[x][0]++;
A[x][A[x][0]]=y;
AT[y][0]++;
AT[y][A[y][0]]=x;
}
for(int i=1;i<=n;i++){
if(!viz[i]){
dfs(i);
}
}
// for(int i=n;i>0;i--)
// cout<<postordine[i]<<" ";
for(int i=n;i>0;i--){
if(viz[postordine[i]]>0){
nrm++;
dfst(postordine[i],nrm);
//cout<<'\n';
}
}
// for(int i=n;i>0;i--)
// cout<<viz[i]<<" ";
fout<<nrm;
fout<<'\n';
for(int i=n;i>0;i--){
if(viz[postordine[i]]<0){
//nrm++;
dfst2(postordine[i]);
fout<<'\n';
}
}
return 0;
}