Pagini recente » Borderou de evaluare (job #2759968) | Cod sursa (job #434949) | Cod sursa (job #445438) | Cod sursa (job #1354057) | Cod sursa (job #1881087)
# include <fstream>
# include <vector>
# define DIM 100002
using namespace std;
ifstream fin("plimbare.in");
ofstream fout("plimbare.out");
vector<int> Lista[DIM],nrctc[DIM];
int /*v[DIM][DIM],*/Marcat[DIM],aux[DIM],maxim[DIM],poz[DIM],low[DIM],s[DIM];
int n,i,r,u,ctc,x,y;
void atribuie(int a[],int b[]){
for(int i=0;i<=b[0];i++)
a[i]=b[i];
}
void tarjan(int nc){
r++;
poz[nc]=r;
low[nc]=r;
s[++u]=nc;
Marcat[nc]=1;
for(int i=0;i<Lista[nc].size();i++){
int nv=Lista[nc][i];
if(poz[nv]==0)
tarjan(nv);
if(Marcat[nv])
low[nc]=min(low[nc],low[nv]);
}
if(poz[nc]==low[nc]){
ctc++;
aux[0]=0;
while(s[u]!=nc){
nrctc[ctc].push_back(s[u]);
aux[++aux[0]]=s[u];
Marcat[s[u]]=0;
u--;
}
nrctc[ctc].push_back(s[u]);
Marcat[s[u]]=0;
u--;
if(maxim[0]<aux[0])
atribuie(maxim,aux);
}
}
int main () {
int m;
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y;
Lista[x].push_back(y);
//v[x][y]=1;
}
tarjan(1);
fout<<ctc<<"\n";
for(i=1;i<=ctc;i++){
for(int j=0;j<nrctc[i].size();j++)
fout<<nrctc[i][j]<<" ";
fout<<"\n";
}
return 0;
}