Cod sursa(job #2692257)

Utilizator d3nis01Denis Deaconu d3nis01 Data 1 ianuarie 2021 22:03:24
Problema Componente tare conexe Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int s[100], p[100], n, a[100][100], nrc, ctc[100];

void Citire()
{
    fin >> n;
    int nod1, nod2;
    while (fin >> nod1 >> nod2)
        a[nod1][nod2] = 1;
}

void df1(int x)
{
    s[x] = 1;
    for(int i =1 ; i <= n ; i ++)
        if(s[i] == 0 && a[x][i] == 1)
            df1(i);
}

void df2(int x)
{
    p[x] = 1;
    for(int i =1 ; i <= n ; i ++)
        if(p[i] == 0 && a[i][x] == 1)
            df2(i);
}

int main()
{
    Citire();

    for(int i = 1 ; i <= n ; ++i)
        if(ctc[i] == 0)
        {
            for(int j = 1; j <= n ; ++j)
                s[j] = p[j] = 0;
            nrc ++;
            df1(i); df2(i);
            for(int j = 1; j <= n ; ++j)
                if(s[j] == 1 && p[j] == 1)
                    ctc[j] = nrc;
        }

    fout << nrc << endl;

    for (int i = 1; i <= nrc; i++)
    {
        for (int j = 1; j <= n; j++)
            if (ctc[j] == i)
                fout << j << ' ';
        fout << endl;
    }


}