Cod sursa(job #1481136)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 3 septembrie 2015 21:16:34
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#define MAXN 100000
#define MAXM 200000
int k, sef, viz[MAXN+1], ok[MAXN+1], val[MAXM+1], e[MAXM+1], next[MAXM+1], urm[MAXM+1], lista[MAXN+1], list[MAXN+1], l[MAXN+1], last[MAXN+1], v[MAXN+1];
void dfs1(int x){
    int p=lista[x];
    viz[x]=1;
    while(p){
        if(viz[val[p]]==0){
            dfs1(val[p]);
        }
        p=next[p];
    }
    v[k++]=x;
}
void dfs2(int x){
    int p=list[x];
    ok[x]=1;
    last[x]=l[sef];
    l[sef]=x;
    while(p){
        if(ok[e[p]]==0){
            dfs2(e[p]);
        }
        p=urm[p];
    }
}
int main(){
    int n, m, i, ans;
    FILE *fin, *fout;
    fin=fopen("ctc.in", "r");
    fout=fopen("ctc.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d", &e[i], &val[i]);
        next[i]=lista[e[i]];
        lista[e[i]]=i;
        urm[i]=list[val[i]];
        list[val[i]]=i;
    }
    for(i=1; i<=n; i++){
        if(viz[i]==0){
            dfs1(i);
        }
    }
    ans=0;
    for(i=n-1; i>=0; i--){
        if(ok[v[i]]==0){
            sef=v[i];
            dfs2(v[i]);
            ans++;
        }
    }
    fprintf(fout, "%d\n", ans);
    for(i=1; i<=n; i++){
        if(l[i]){
            fprintf(fout, "%d", l[i]);
            l[i]=last[l[i]];
            while(l[i]){
                fprintf(fout, " %d", l[i]);
                l[i]=last[l[i]];
            }
            fprintf(fout, "\n");
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}