Cod sursa(job #2806126)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:18:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <deque>
#include <vector>

using namespace std;
FILE* f, * g;
int n, m;
int starttr[100002], start[100002], t[2][200002], ttr[2][200002], sol;
bool viz[100002];
int q[100002];
vector <int> a[100002];

void dfstr(int nod)
{
    int poz, vecin;
    viz[nod] = 1;
    poz = starttr[nod];
    while (poz)
    {
        vecin = ttr[0][poz];
        if (!viz[vecin])
            dfstr(vecin);
        poz = ttr[1][poz];
    }
    a[sol].push_back(nod);

}
void dfs(int nod)
{
    int poz, vecin;
    poz = start[nod];
    viz[nod] = 1;
    while (poz)
    {
        vecin = t[0][poz];
        if (!viz[vecin])
            dfs(vecin);

        poz = t[1][poz];
    }
    q[++q[0]] = nod;
}
int main()
{
    f = fopen("ctc.in", "r");
    g = fopen("ctc.out", "w");
    fscanf(f, "%d %d", &n, &m);
    int k1 = 0, k2 = 0, x, y;
    for (int i = 1;i <= m;++i)
    {
        fscanf(f, "%d %d", &x, &y);
        t[0][++k1] = y;
        t[1][k1] = start[x];
        start[x] = k1;
        ttr[0][++k2] = x;
        ttr[1][k2] = starttr[y];
        starttr[y] = k2;
    }
    for (int i = 1;i <= n;++i)
        if (!viz[i])
            dfs(i);
    for (int i = 1;i <= n;++i)
        viz[i] = 0;
    for (int i = n;i >= 1;--i)
        if (!viz[q[i]])
            ++sol, dfstr(q[i]);
    fprintf(g, "%d\n", sol);
    for (int i = 1;i <= sol;++i)
    {
        for (int j = 0;j < a[i].size();++j)
            fprintf(g, "%d ", a[i][j]);
        fprintf(g, "\n");
    }
    fclose(f);
    fclose(g);
    return 0;
}