Cod sursa(job #2979232)

Utilizator AlbuDariusAlbu Darius AlbuDarius Data 14 februarie 2023 20:42:04
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a[2][20005], start[10005], a1[2][20005], start1[10005], nr, p[10005], mi[10005], viz[10005], sol[10005], lg;
void df1(int nod);
void df2(int nod);
void plusminus();
int main()
{
    int i, x, y;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y;
        a[0][i] = y;
        a[1][i] = start[x];
        start[x] = i;
        a1[0][i] = x;
        a1[1][i] = start1[y];
        start1[y] = i;
    }
    plusminus();
    fout << nr << "\n";
    for (i = 1; i <= lg; i++)
        if (sol[i] > 0)
            fout << sol[i] << " ";
        else
            fout << "\n";
    return 0;
}
void df1(int nod)
{
    int x;
    p[nod] = 1;
    x = start[nod];
    while (x) {
        if (p[a[0][x]] == 0)
            df1(a[0][x]);
        x = a[1][x];
    }
}
void df2(int nod)
{
    int x;
    mi[nod] = 1;
    x = start1[nod];
    while (x) {
        if (mi[a1[0][x]] == 0)
            df2(a1[0][x]);
        x = a1[1][x];
    }
}
void plusminus()
{
    int i, j;
    for (i = 1; i <= n; i++)
        if (viz[i] == 0) {
            nr++;
            for (j = 1; j <= n; j++)
                p[j] = mi[j] = 0;
            df1(i);
            df2(i);
            for (j = 1; j <= n; j++)
                if (p[j] && mi[j]) {
                    sol[++lg] = j;
                    viz[j] = 1;
                }
            sol[++lg] = -1;
        }
}