Cod sursa(job #2979242)

Utilizator AlbuDariusAlbu Darius AlbuDarius Data 14 februarie 2023 20:52:21
Problema Componente tare conexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a[2][200005], start[100005], a1[2][200005], start1[100005], nr, p[100005], mi[100005], viz[100005];
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";
    return 0;
}
void df1(int nod)
{
    int x;
    p[nod] = nr;
    x = start[nod];
    while (x) {
        if (p[a[0][x]] != nr)
            df1(a[0][x]);
        x = a[1][x];
    }
}
void df2(int nod)
{
    int x;
    mi[nod] = nr;
    x = start1[nod];
    while (x) {
        if (mi[a1[0][x]] != nr)
            df2(a1[0][x]);
        x = a1[1][x];
    }
}
void plusminus()
{
    int i, j;
    for (i = 1; i <= n; i++)
        if (viz[i] == 0) {
            viz[i] = nr;
            nr++;
            df1(i);
            df2(i);
            for (j = 1; j <= n; j++)
                if (p[j] == nr && mi[j] == nr)
                    viz[j] = nr;
        }
}