Pagini recente » Cod sursa (job #782120) | Cod sursa (job #230732) | Cod sursa (job #2443295) | Cod sursa (job #356178) | Cod sursa (job #1601339)
#include<stdio.h>
using namespace std;
FILE *f1=fopen("ctc.in","r");
FILE *f2=fopen("ctc.out","w");
int n,m,v[100001],ordine[100001],timp[100001],i,nrc,k,j;
struct nod{
int inf;
nod *urm;
}*L1[100001],*L2[100001];
void adaugaresf(int val,nod *&vf){
nod *q;
q=new nod;
q->inf=val;
q->urm=vf;
vf=q;
}
void citire(){
fscanf(f1,"%d%d",&n,&m);
int k,a,b;
for (k=1;k<=n;k++){
L1[k]=0;
L2[k]=0;
}
for (k=1;k<=m;k++){
fscanf(f1,"%d%d",&a,&b);
adaugaresf(b,L1[a]);
adaugaresf(a,L2[b]);
}
fclose(f1);
}
void dfs(int k,int nr){
v[k]=nr;
nod *q;
q=L2[k];
while(q!=0){
if (v[q->inf]==0) dfs(q->inf,nr);
q=q->urm;
}
}
void dfs_timp(int k,int t){
nod *q;
q=L1[k];
while(q!=0){
if (v[q->inf]==0){
v[q->inf]=1;
dfs_timp(q->inf,t+1);
}
q=q->urm;
}
timp[k]=t;
}
int main(){
citire();
for (i=1;i<=n;i++)
if (v[i]==0)
dfs_timp(i,1);
for (i=1;i<=n;i++){
k=timp[i];
ordine[k]=i;
}
for (i=1;i<=n;i++)
v[i]=0;
for (i=1;i<=n;i++){
k=ordine[i];
if (v[k]==0) {
nrc++;
dfs(k,nrc);
}
}
fprintf(f2,"%d\n",nrc);
for (i=1;i<=nrc;i++){
for (j=1;j<=n;j++)
if (v[j]==i) fprintf(f2,"%d ",j);
fprintf(f2,"\n");
}
fclose(f2);
return 0;
}