Cod sursa(job #2928377)

Utilizator BVLUBogdan Ivan BVLU Data 22 octombrie 2022 20:45:58
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int a[100][100], n, m, nod;
bool viz[100];
vector < vector <int> > v;

void citire()
{
    ifstream f( "ctc.in" );
    f >> n >> m;
    for( int i = 0; i < m; ++i )
    {
        int x, y;
        f >> x >> y;
        a[--x][--y] = 1;
    }
    f.close();
}

void royWarshal()
{
    for( int k = 0; k < n; ++k )
        for( int i = 0; i < n; ++i )
            for( int j = 0; j < n; ++j )
                if( a[i][k] == 1 && a[k][j] == 1 )
                    a[i][j] = 1;
}

void CTC()
{
    for( int i = 0; i < n; ++i )
        if( !viz[i] )
        {
            viz[i] = true;
            v.push_back( {} );
            v[ v.size() - 1 ].push_back( i + 1 );
            for( int j = 0; j < n; ++j )
                if( a[i][j] && a[j][i] && !viz[j] )
                    v[ v.size() - 1 ].push_back( j + 1 ), viz[j] = true;
        }
}

int main()
{
    citire();
    royWarshal();
    CTC();

    int maxim = 0;
    for( int i = 0; i < v.size(); ++i )
        if( v[i].size() > maxim )
            maxim = v[i].size();

    ofstream g( "ctc.out" );

    for( int i = 0; i < v.size(); ++i )
        if( v[i].size() == maxim )
        {
            for( int j = 0; j < v[i].size(); ++j )
                g << v[i][j] << " ";
            g << endl;
        }
    return 0;
}