Cod sursa(job #3349071)

Utilizator comanandreiComan Andrei comanandrei Data 25 martie 2026 12:02:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <stdio.h>

#define MAXN 100000
#define MAXM 200000

using namespace std;

FILE *fin, *fout;

struct cell{
    int v, next;
};

struct node{
    int adj;
    int time_in;
    int low;
    bool on_stack;
};

struct my_stack{
    int v[MAXN+1];
    int pointer=0;
    void push(int val){
        v[++pointer]=val;
    }
    void pop(){
        pointer--;
    }
    int top(){
        return v[pointer];
    }
};

cell my_list[MAXM+1];
node nd[MAXN+1];
my_stack st;
int n, m, time, nr_ctc, find_ctc;

int my_min(int a, int b){
    return a<b?a:b;
}

void write_ctc_and_pop(int last){
    int v;
    do{
        v=st.top();
        st.pop();
        fprintf(fout, "%d ", v);
        nd[v].on_stack=false;
    }while(v!=last);
    fprintf(fout, "\n");
}

void pop_and_count(int last){
    int v;
    do{
        v=st.top();
        st.pop();
        nd[v].on_stack=false;
    }while(v!=last);
    nr_ctc++;
}

void dfs(int u){
    nd[u].time_in=nd[u].low=++time;
    nd[u].on_stack=true;
    st.push(u);
    for(int ptr=nd[u].adj;ptr;ptr=my_list[ptr].next){
        int v=my_list[ptr].v;
        if(!nd[v].time_in){
            dfs(v);
            nd[u].low=my_min(nd[u].low, nd[v].low);
        }
        else if(nd[v].on_stack){
            nd[u].low=my_min(nd[u].low, nd[v].time_in);
        }
    }
    if(nd[u].low==nd[u].time_in){
        if(find_ctc){
            write_ctc_and_pop(u);
        }
        else{
            pop_and_count(u);
        }
    }
}

void dfs_driver(){
    for(int u=1;u<=n;u++){
        if(!nd[u].time_in){
            dfs(u);
        }
    }
    find_ctc++;
}

void reset(){
    for(int u=1;u<=n;u++){
        nd[u].time_in=nd[u].low=0;
    }
}

void add_edge(int u, int v){
    static int pos=1;
    my_list[pos]={v, nd[u].adj};
    nd[u].adj=pos++;
}

void read_graph(){
    int u, v;
    fin=fopen("ctc.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(int i=0;i<m;i++){
        fscanf(fin, "%d%d", &u, &v);
        add_edge(u, v);
    }
    fclose(fin);
}

int main()
{
    read_graph();
    dfs_driver();
    reset();
    fout=fopen("ctc.out", "w");
    fprintf(fout, "%d\n", nr_ctc);
    dfs_driver();
    fclose(fout);
    return 0;
}