Cod sursa(job #2927638)

Utilizator Anastasia7Anastasia Anastasia7 Data 20 octombrie 2022 22:47:03
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
using namespace std;

int n , a[10001][10001], ctc[20001] , s[20001], p[20001], nrc;
ifstream f("ctc.in");
ofstream g("ctc.out");
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()
{
    int i , j , m;
    f >> n >> m;
    while( m )
    {
        f >> i >> j;
        a[i][j] = 1;
        m --;
    }
    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;
        }
    g << nrc << endl;

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

    return 0;
}