Cod sursa(job #3296205)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 12 mai 2025 10:07:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;
#define MAXN 100000
vector<int> v[MAXN + 1];
vector<int> vtr[MAXN + 1];
vector<int> ctc[MAXN + 1];
char f[MAXN + 1];
int post[MAXN];
int nrn, nrc;
void dfs(int nod) {
    int i, x, nr;
    f[nod] = 1;
    nr = v[nod].size();
    for (i = 0; i < nr; i++) {
        x = v[nod][i];
        if (f[x] == 0) {
            dfs(x);
        }
    }
    post[nrn] = nod;
    nrn++;
}
void dfs2(int nod) {
    int i, x, nr;
    f[nod] = 1;
    ctc[nrc].push_back(nod);
    nr = vtr[nod].size();
    for (i = 0; i < nr; i++) {
        x = vtr[nod][i];
        if (f[x] == 0) {
            dfs2(x);
        }
    }
}
int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y, nr, j;
    fin = fopen("ctc.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &x, &y);
        v[x].push_back(y);
        vtr[y].push_back(x);
    }
    fclose(fin);
    for (i = 1; i <= n; i++) {
        if (f[i] == 0) {
            dfs(i);
        }
    }

    for (i = 1; i <= n; i++) {
        f[i] = 0;
    }
    //al doilea dfs
    nrc = 0;
    for (i = n - 1; i >= 0; i--) {
        if (f[post[i]] == 0) {
            dfs2(post[i]);
            nrc++;
        }
    }
    fout = fopen("ctc.out", "w");
    fprintf(fout, "%d\n", nrc);
    for (i = 0; i < nrc; i++) {
        nr = ctc[i].size();
        for (j = 0; j < nr; j++) {
            fprintf(fout, "%d ", ctc[i][j]);
        }
        fputc('\n', fout);
    }
    fclose(fout);
    return 0;
}