Cod sursa(job #1713191)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 4 iunie 2016 22:00:43
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100100
#define M 200100
#define vec lis[i].val
#define revvec revlis[i].val

using namespace std;


int head[N],revhead[N],postnum[N],ord[2*N];
bool viz[N];
int ifin,revifin;
int n;
struct muc{
    int val,next;
};

struct muc lis[M],revlis[M];



void Add_arc(int x,int y);
void revAdd_arc(int x,int y);

int cnt;
void bfs(int k){
    int i;

    viz[k]=1;
    for(i=head[k] ;i!=-1;i=lis[i].next){
        if(viz[vec]==0){
            bfs(vec);
        }
    }
    postnum[cnt++]=k;
}
int nrnod;
void revdfs(int k) {
    int i;

    viz[k]=1;
    for (i = revhead[k]; i!=-1 ; i=revlis[i].next){
        if (viz[revvec] == 0){
            revdfs(revvec);
        }
    }
    ord[nrnod++]=k;
}


void Init(){
    memset(head,-1,(n+1)*sizeof(int) );
    memset(revhead,-1,(n+1)*sizeof(int) );
    ifin=revifin=cnt=0;
}

int main(){
    int m,i,x,y;
    int nrctc=0;

    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    scanf("%d%d",&n,&m);

    Init();

    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        Add_arc(x,y);
        revAdd_arc(y,x);
    }

    for(i=1;i<=n;i++){
        if(viz[i]==0){
            bfs(i);
        }
    }

    memset(viz,0,(n+1)*sizeof(int));

    for(i=cnt-1;i>=0;i--){
        if(viz[ postnum[i] ]==0){
            revdfs(postnum[i]);
            ord[nrnod++]=-1;
            nrctc++;
        }
    }

    printf("%d\n",nrctc);
    for(i=0;i<nrnod;i++){
        if(ord[i]==-1){
            printf("\n");
            continue;
        }
        printf("%d ",ord[i]);
    }

    return 0;
}

void Add_arc(int x,int y){
    lis[ifin].val=y;
    lis[ifin].next=head[x];
    head[x]=ifin;
    ifin++;
}

void revAdd_arc(int x,int y){
    revlis[revifin].val=y;
    revlis[revifin].next=revhead[x];
    revhead[x]=revifin;
    revifin++;
}