Cod sursa(job #3296221)

Utilizator Tibi201eweREWR Tibi201 Data 12 mai 2025 10:20:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <vector>
#define MAXN 100000

int q[MAXN], k, last, n;
std::vector <int> edges[MAXN+1];
std::vector <int> redges[MAXN+1];
std::vector <int> sol[MAXN+1];
int t;
int top[MAXN+1], j;
int f[MAXN+1];

void dfs1(int node){
    f[node]=1;
    for(auto x : edges[node])
        if(!f[x])
            dfs1(x);
    top[j++]=node;
}

void reverse(){
    int i;
    for(i=1; i<=n; i++)
        for(auto x : edges[i])
            redges[x].push_back(i);
}

void dfs2(int node){
    f[node]=-1;
    sol[t].push_back(node);
    for(auto x : redges[node])
        if(f[x]!=-1)
            dfs2(x);
}

void solve(){
    int i;
    for(i=1; i<=n; i++){
        if(!f[i])
            dfs1(i);
    }
    reverse();
    for(i=n-1; i>=0; i--){
        if(f[top[i]]!=-1){
            dfs2(top[i]);
            t++;
        }
    }
    FILE *fout=fopen("ctc.out", "w");
    fprintf(fout, "%d\n", t);
    for(i=0; i<t; i++){
        for(auto x : sol[i]){
            fprintf(fout, "%d ", x);
        }
        fprintf(fout, "\n");
    }
    fclose(fout);
}

int main()
{
    FILE *fin;
    int m,i,x,y;
    fin=fopen("ctc.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d", &x, &y);
        edges[x].push_back(y);
    }
    solve();
    return 0;
}