Cod sursa(job #2806124)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:17:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <vector>
#define N 100002
#include <deque>

using namespace std;
FILE* f, * g;

vector <int> graph[N], grapht[N], ctc[N];
int sol;
int elms[N];
bool viz[N];
void dfs(int nod)
{
    viz[nod] = 1;
    for (int i = 0;i < grapht[nod].size();++i)
        if (!viz[grapht[nod][i]])
            dfs(grapht[nod][i]);
    ctc[sol].push_back(nod);
}

void topo(int nod)
{
    viz[nod] = 1;
    for (int i = 0;i < graph[nod].size();++i)
        if (!viz[graph[nod][i]])
            topo(graph[nod][i]);
    elms[++elms[0]] = nod;
}
int main()
{
    f = fopen("ctc.in", "r");
    g = fopen("ctc.out", "w");
    int n, m;
    fscanf(f, "%d %d", &n, &m);
    int x, y;
    for (int i = 1;i <= m;++i)
    {
        fscanf(f, "%d %d", &x, &y);
        graph[x].push_back(y);
        grapht[y].push_back(x);
    }
    for (int i = 1;i <= n;++i)
        if (!viz[i])
            topo(i);
    for (int i = 1;i <= n;++i)
        viz[i] = 0;
    for (int i = elms[0];i >= 1;--i)
        if (!viz[elms[i]])
            ++sol, dfs(elms[i]);
    fprintf(g, "%d\n", sol);
    for (int i = 1;i <= sol;++i)
    {
        for (int j = 0;j < ctc[i].size();++j)
            fprintf(g, "%d ", ctc[i][j]);
        fprintf(g, "\n");
    }

    fclose(f);
    fclose(g);
    return 0;
}