Cod sursa(job #2349296)

Utilizator DavidLDavid Lauran DavidL Data 20 februarie 2019 12:48:32
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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;
bool vizg[NMAX], vizh[NMAX];
int nr;

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

void dfsH(int nod)
{
    vizh[nod] = 1;
    for (auto v: H[nod])
    {
        if (!comp[v] && !vizh[v])
            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);

            for (int j = 1; j <= n; j++)
                if (!comp[j] && vizg[j] && vizh[j])
                {
                    comp[j] = nr;
                    p[nr].push_back(j);
                }
            for (int j = 1; j <= n; j++)
                vizg[j] = vizh[j] = 0;
        }
    }

    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;
}