Pagini recente » Cod sursa (job #2378449) | Cod sursa (job #951774) | Cod sursa (job #2121268) | Cod sursa (job #2229789) | Cod sursa (job #744267)
Cod sursa(job #744267)
#include <stdio.h>
#include <vector>
using namespace std;
#define FI fopen("ctc.in","r")
#define FO fopen("ctc.out","w")
vector<long> nod[100001],sol[100001];
long n,st[100000],nr,h[100001],stSize,nrSol,val[100001];
void citeste(FILE *f) {
long m,i,a,b;
fscanf(f,"%li%li",&n,&m);
for(i=0;i<m;i++) {
fscanf(f,"%li%li",&a,&b);
nod[a].push_back(b);
}
}
void emptySt(long poz) {
long i;
for(i=poz;i<=stSize;i++)
sol[nrSol].push_back(st[i]);
nrSol++;
stSize=poz-1;
}
long tarjan(long nodA,long poz,long niv) {
long lim=nod[nodA].size(),i,x;
st[poz]=nodA;
h[nodA]=niv;
val[nodA]=niv;
stSize=poz;
for(i=0;i<lim;i++)
if(val[nod[nodA][i]]) {
if(val[nod[nodA][i]]<val[nodA])
val[nodA]=val[nod[nodA][i]];
}
else
if(h[nod[nodA][i]]==0) {
x=tarjan(nod[nodA][i],stSize+1,niv+1);
if(x<val[nodA])
val[nodA]=x;
}
if(val[nodA]==h[nodA])
emptySt(poz);
return val[nodA];
}
void scrie(FILE *f) {
int i,j,lim;
fprintf(f,"%li\n",nrSol);
for(i=0;i<nrSol;i++) {
lim=sol[i].size();
for(j=0;j<lim;j++)
fprintf(f,"%li ",sol[i][j]);
fprintf(f,"\n");
}
}
int main() {
long i;
citeste(FI);
for(i=1;i<=n;i++)
if(h[i]==0)
tarjan(i,0,1);
scrie(FO);
return 0;
}