Cod sursa(job #2349308)

Utilizator DavidLDavid Lauran DavidL Data 20 februarie 2019 12:55:46
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <vector>
using namespace std;

const int NMAX = 1e5 + 5;

vector <int> G[NMAX], H[NMAX];
vector <int> p[NMAX];
int comp[NMAX];
int n, m;
int vizg[NMAX];
int nr;

void dfsG(int nod)
{
    vizg[nod] = nr;
    for (auto v: G[nod])
    {
        if (!comp[v] && vizg[v] < nr)
            dfsG(v);
    }
}

void dfsH(int nod)
{
    p[nr].push_back(nod);
    comp[nod] = nr;

    for (auto v: H[nod])
    {
        if (!comp[v] && vizg[v] == nr)
        {
            dfsH(v);
        }
    }
}

int main()
{
    FILE *fi, *fo;
    fi = fopen("ctc.in", "r");
    fo = fopen("ctc.out", "w");

    fscanf(fi, "%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        fscanf(fi, "%d%d", &u, &v);
        G[u].push_back(v);
        H[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!comp[i])
        {
            nr++;
            dfsG(i);
            dfsH(i);
        }
    }

    fprintf(fo, "%d\n", nr);

    for (int i = 1; i <= nr; i++)
    {
        for (auto x: p[i])
            fprintf(fo, "%d ", x);
        fprintf(fo, "\n");
    }

    return 0;
}