Untitled

#include <algorithm>
#include <cstring>
#include <initializer_list>
#include <iostream>
#include <sstream>
#include <stdexcept>

template< typename T >
class Vector
{
public:
    Vector();
    Vector( std::initializer_list< T > init );
    Vector( const Vector& other );
    Vector( Vector&& other ) noexcept;

    explicit Vector( const T& value );
    explicit Vector( size_t size, const T& value );
    Vector( T* first, T* last );

    ~Vector();

    Vector& operator=( const Vector& other );
    Vector& operator=( Vector&& other ) noexcept;

    T& operator[]( size_t index );
    const T& operator[]( size_t index ) const;

    bool operator==( const Vector& other ) const;
    bool operator!=( const Vector& other ) const;

    void push_back( const T& value );
    void push_back( T&& value );
    void pop_back();
    void clear();

    size_t size() const;
    size_t capacity() const;
    bool empty() const;
    void reserve( size_t newCapacity );

    T* begin();
    T* end();
    const T* begin() const;
    const T* end() const;

private:
    void reallocate( size_t newCapacity );

    T* data_;
    size_t size_;
    size_t capacity_;
};

template< typename T >
Vector< T >::Vector() : data_( nullptr ), size_( 0 ), capacity_( 0 )
{
    // Empty body.
}

template< typename T >
Vector< T >::Vector( std::initializer_list< T > init ) : Vector()
{
    for( const T& item : init )
    {
        push_back( item );
    }
}

template< typename T >
Vector< T >::Vector( const Vector& other ) : data_( nullptr ), size_( 0 ), capacity_( 0 )
{
    reallocate( other.capacity_ );
    size_ = other.size_;
    for( size_t i = 0; i < size_; ++i )
    {
        data_[ i ] = other.data_[ i ];
    }
}

template< typename T >
Vector< T >::Vector( Vector&& other ) noexcept : data_( other.data_ ), size_( other.size_ ), capacity_( other.capacity_ )
{
    other.data_ = nullptr;
    other.size_ = 0;
    other.capacity_ = 0;
}

template< typename T >
Vector< T >::Vector( const T& value ) : data_( new T[ value ] ), size_( value ), capacity_( value )
{
    for( size_t i = 0; i < size_; ++i )
    {
        data_[ i ] = value;
    }
}

template< typename T >
Vector< T >::Vector( size_t size, const T& value ) : data_( new T[ size ] ), size_( size ), capacity_( size )
{
    for( size_t i = 0; i < size_; ++i )
    {
        data_[ i ] = value;
    }
}

template< typename T >
Vector< T >::Vector( T* first, T* last )
{
    size_ = last - first;
    capacity_ = size_;
    data_ = new T[ capacity_ ];
    std::copy( first, last, data_ );
}

template< typename T >
Vector< T >::~Vector()
{
    delete [] data_;
}

template< typename T >
Vector< T >& Vector< T >::operator=( const Vector& other )
{
    if( this != &other )
    {
        delete [] data_;
        reallocate( other.capacity_ );
        size_ = other.size_;
        for( size_t i = 0; i < size_; ++i )
        {
            data_[ i ] = other.data_[ i ];
        }
    }

    return *this;
}

template< typename T >
Vector< T >& Vector< T >::operator=( Vector&& other ) noexcept
{
    if( this != &other )
    {
        delete [] data_;
        data_ = other.data_;
        size_ = other.size_;
        capacity_ = other.capacity_;
        other.data_ = nullptr;
        other.size_ = 0;
        other.capacity_ = 0;
    }

    return *this;
}

template< typename T >
T& Vector< T >::operator[]( size_t index )
{
    if( index >= size_ )
    {
        throw std::out_of_range( "Index out of range!" );
    }

    return data_[ index ];
}

template< typename T >
const T& Vector< T >::operator[]( size_t index ) const
{
    if( index >= size_ )
    {
        throw std::out_of_range( "Index out of range!" );
    }

    return data_[ index ];
}

template< typename T >
bool Vector< T >::operator==( const Vector& other ) const
{
    if( size_ != other.size_ )
    {
        return false;
    }
    for( size_t i = 0; i < size_; ++i )
    {
        if( data_[ i ] != other.data_[ i ] )
        {
            return false;
        }
    }

    return true;
}

template< typename T >
bool Vector< T >::operator!=( const Vector& other ) const
{
    return !( *this == other );
}

template< typename T >
void Vector< T >::push_back( const T& value )
{
    if( size_ >= capacity_ )
    {
        reallocate( capacity_ == 0 ? 1 : 2 * capacity_ );
    }

    data_[ size_++ ] = value;
}

template< typename T >
void Vector< T >::push_back( T&& value )
{
    if( size_ >= capacity_ )
    {
        reallocate( capacity_ == 0 ? 1 : 2 * capacity_ );
    }

    data_[ size_++ ] = std::move( value );
}

template< typename T >
void Vector< T >::pop_back()
{
    if( size_ > 0 )
    {
        --size_;
    }
}

template< typename T >
void Vector< T >::clear()
{
    size_ = 0;
}

template< typename T >
size_t Vector< T >::size() const
{
    return size_;
}

template< typename T >
size_t Vector< T >::capacity() const
{
    return capacity_;
}

template< typename T >
bool Vector< T >::empty() const
{
    return size_ == 0;
}

template< typename T >
void Vector< T >::reserve( size_t newCapacity )
{
    if( newCapacity > capacity_ )
    {
        reallocate( newCapacity );
    }
}

template< typename T >
T* Vector< T >::begin()
{
    return data_;
}

template< typename T >
T* Vector< T >::end()
{
    return data_ + size_;
}

template< typename T >
const T* Vector< T >::begin() const
{
    return data_;
}

template< typename T >
const T* Vector< T >::end() const
{
    return data_ + size_;
}

template< typename T >
void Vector< T >::reallocate( size_t newCapacity )
{
    T* newData = new T[ newCapacity ];
    for( size_t i = 0; i < size_; ++i )
    {
        newData[ i ] = std::move( data_[ i ] );
    }
    delete [] data_;
    data_ = newData;
    capacity_ = newCapacity;
}

template< typename T, typename Container = Vector< T > >
class Queue
{
public:
    Queue() = default;

    T& front();
    const T& front() const;
    T& back();
    const T& back() const;
    void push( const T& value );
    void push( T&& value );
    void pop();

    bool empty() const;
    size_t size() const;

private:
    Container container;
};

template< typename T, typename Container >
T& Queue< T, Container >::front()
{
    return container[ 0 ];
}

template< typename T, typename Container >
const T& Queue< T, Container >::front() const
{
    return container[ 0 ];
}

template< typename T, typename Container >
T& Queue< T, Container >::back()
{
    return container[ container.size() - 1 ];
}

template< typename T, typename Container >
const T& Queue< T, Container >::back() const
{
    return container[ container.size() - 1 ];
}

template< typename T, typename Container >
void Queue< T, Container >::push( const T& value )
{
    container.push_back( value );
}

template< typename T, typename Container >
void Queue< T, Container >::push( T&& value )
{
    container.push_back( std::move( value ) );
}

template< typename T, typename Container >
void Queue< T, Container >::pop()
{
    if( !container.empty() )
    {
        for( size_t i = 1; i < container.size(); ++i )
        {
            container[ i - 1 ] = std::move( container[ i ] );
        }
        container.pop_back();
    }
}

template< typename T, typename Container >
bool Queue< T, Container >::empty() const
{
    return container.empty();
}

template< typename T, typename Container >
size_t Queue< T, Container >::size() const
{
    return container.size();
}

class String
{
public:
    String();
    explicit String( const char* str );

    ~String();

    String& operator=( const String& other );

    char& operator[]( size_t index );
    const char& operator[]( size_t index ) const;
    String& operator=( const char* str );
    String& operator+=( char c );

    size_t length() const;
    const char* c_str() const;

    friend std::ostream& operator<<( std::ostream& os, const String& str )
    {
        if( str.buffer_ != nullptr )
        {
            os << str.buffer_;
        }

        return os;
    }

    friend void readLine( std::istream& is, String& str )
    {
        char c;
        str = "";

        while( is.get( c ) && c != '\n' )
        {
            str += c;
        }
    }

private:
    char* buffer_;
};

String::String() : buffer_( nullptr )
{
    // Empty body.
}

String::String( const char* str )
{
    if( str != nullptr )
    {
        buffer_ = new char[strlen( str ) + 1 ];
        strcpy( buffer_, str );
    }
    else
    {
        buffer_ = nullptr;
    }
}

String::~String()
{
    delete[] buffer_;
}

String& String::operator=( const String& other )
{
    if( this != &other )
    {
        delete[] buffer_;
        if( other.buffer_ != nullptr )
        {
            buffer_ = new char[strlen( other.buffer_ ) + 1 ];
            strcpy( buffer_, other.buffer_ );
        }
        else
        {
            buffer_ = nullptr;
        }
    }

    return *this;
}

char& String::operator[]( size_t index )
{
    if( buffer_ != nullptr && index < strlen( buffer_ ) )
    {
        return buffer_[ index ];
    }
    else
    {
        std::cerr << "Index out of range\n";
        exit( 1 );
    }
}

const char& String::operator[]( size_t index ) const
{
    if( buffer_ != nullptr && index < strlen( buffer_ ) )
    {
        return buffer_[ index ];
    }
    else
    {
        std::cerr << "Index out of range\n";
        exit( 1 );
    }
}

String& String::operator=( const char* str )
{
    if( buffer_ != nullptr )
    {
        delete[] buffer_;
    }

    if( str != nullptr )
    {
        buffer_ = new char[ strlen( str ) + 1 ];
        strcpy( buffer_, str );
    }
    else
    {
        buffer_ = nullptr;
    }

    return *this;
}

String& String::operator+=( char c )
{
    size_t newLength = length() + 1;
    char* newBuffer = new char[ newLength + 1 ];

    if( buffer_ != nullptr )
    {
        strcpy( newBuffer, buffer_ );
        newBuffer[ newLength - 1 ] = c;
        newBuffer[ newLength ] = '\0';
        delete[] buffer_;
    }
    else
    {
        newBuffer[ 0 ] = c;
        newBuffer[ 1 ] = '\0';
    }

    buffer_ = newBuffer;

    return *this;
}

size_t String::length() const
{
    return ( buffer_ != nullptr ) ? strlen( buffer_ ) : 0;
}

const char* String::c_str() const
{
    return buffer_;
}

using Adjacency = Vector< int >;

class Graph
{
public:
    Graph() : number_of_vertices( 0 )
    {
        // Empty body.
    }

    explicit Graph( int vertices ) : number_of_vertices( vertices )
    {
        for( int i = 0; i < number_of_vertices; ++i )
        {
            adjacency_list.push_back( Adjacency{} );
        }
    }

    void addEdge( const int& u, const Adjacency& adj );

    Vector< int > degreeSequence();
    int countComponents();
    char isBipartite();
    Vector< int > eccentricity();
    Vector< int > greedyColoring();
    Vector< int > lfColoring();
    int countComplementsEdges();

private:
    void depthSearch( int v, Vector< bool >& visited );

    int number_of_vertices;
    Vector< Adjacency > adjacency_list;
};

#include "Graph.hpp"

#include "Queue.hpp"

#include <algorithm>

void Graph::addEdge( const int& u, const Adjacency& adj )
{
    adjacency_list[ u ] = adj;
}

Vector< int > Graph::degreeSequence()
{
    Vector< int > degrees( number_of_vertices );

    for( int i = 0; i < number_of_vertices; ++i )
    {
        degrees[ i ] = static_cast< int >( adjacency_list[ i ].size() );
    }

    return degrees;
}

int Graph::countComponents()
{
    int components{ 0 };

    Vector< bool > visited( number_of_vertices, false );
    for( int v = 0; v < number_of_vertices; ++v )
    {
        if( !visited[ v ] )
        {
            ++components;
            depthSearch( v, visited );
        }
    }

    return components;
}

char Graph::isBipartite()
{
    Vector< int > colours( number_of_vertices, -1 );
    Queue< std::pair< int, int > > queueColours;

    for( int i = 0; i < number_of_vertices; ++i )
    {
        if( colours[ i ] == -1 )
        {
            queueColours.push( { i, 0 } );
            colours[ i ] = 0;

            while( !queueColours.empty() )
            {
                auto pair = queueColours.front();
                queueColours.pop();
                int v = pair.first;
                int c = pair.second;

                for( int j : adjacency_list[ v ] )
                {
                    if( colours[ j ] == c )
                    {
                        return 'F';
                    }
                    if( colours[ j ] == -1 )
                    {
                        colours[ j ] = !c;
                        queueColours.push( { j, colours[ j ] } );
                    }
                }
            }
        }
    }

    return 'T';
}

Vector< int > Graph::eccentricity()
{
    Vector< int > eccentricities( number_of_vertices, 0 );

    const int adjustLevel = 1;

    for( int v = 0; v < number_of_vertices; ++v )
    {
        Queue< int > queue;
        Vector< bool > visited( number_of_vertices, false );

        queue.push( v );
        visited[ v ] = true;
        int level = 0;

        while( !queue.empty() )
        {
            int size = static_cast< int >( queue.size() );
            while( size-- )
            {
                int curr = queue.front();
                queue.pop();

                eccentricities[ v ] = std::max( eccentricities[ v ], level );

                for( int neighbour : adjacency_list[ curr ] )
                {
                    if( !visited[ neighbour ] )
                    {
                        queue.push( neighbour );
                        visited[ neighbour ] = true;
                    }
                }
            }
            ++level;
        }
        eccentricities[ v ] = level - adjustLevel;
    }

    return eccentricities;
}

Vector< int > Graph::greedyColoring()
{
    Vector< int > verticesColours( number_of_vertices, -1 );

    Vector< bool > availableColours( number_of_vertices, true );

    for( int u = 0; u < number_of_vertices; ++u )
    {
        for( const auto& neighbour : adjacency_list[ u ] )
        {
            if( verticesColours[ neighbour ] != -1 )
            {
                availableColours[ verticesColours[ neighbour ] ] = false;
            }
        }

        int colour = 1;
        for( ; colour < number_of_vertices; ++colour )
        {
            if( availableColours[ colour ] )
            {
                break;
            }
        }

        verticesColours[ u ] = colour;

        for( const auto& neighbour : adjacency_list[ u ] )
        {
            if( verticesColours[ neighbour ] != -1 )
            {
                availableColours[ verticesColours[ neighbour ] ] = true;
            }
        }
    }

    return verticesColours;
}

Vector< int > Graph::lfColoring()
{
    Vector< int > verticesColours( number_of_vertices, -1 );

    Vector< bool > availableColours( number_of_vertices, true );

    Vector< std::pair< int, int > > verticesWihNumber;
    verticesWihNumber.reserve( number_of_vertices );

    for( int u = 0; u < number_of_vertices; ++u )
    {
        verticesWihNumber.push_back( { u, adjacency_list[ u ].size() } );
    }

    std::sort( verticesWihNumber.begin(), verticesWihNumber.end(), [] (
                       const auto &a,
                       const auto &b )
               {
                   if( a.second != b.second )
                       return a.second > b.second;
                   else
                       return a.first < b.first;
               }
    );

    for( const auto &[ u, _ ] : verticesWihNumber )
    {
        std::fill( availableColours.begin(), availableColours.end(), true );

        for( const auto &neighbour : adjacency_list[ u ] )
        {
            if( verticesColours[ neighbour ] != -1 )
            {
                availableColours[ verticesColours[ neighbour ] ] = false;
            }
        }

        int colour = 1;
        for( ; colour < number_of_vertices; ++colour )
        {
            if( availableColours[ colour ] )
            {
                break;
            }
        }

        verticesColours[ u ] = colour;
    }

    return verticesColours;
}

int Graph::countComplementsEdges()
{
    int complementEdges;

    int maxEdges = number_of_vertices * ( number_of_vertices - 1 ) / 2;

    int currentEdges = 0;
    for( const auto& adjacency : adjacency_list )
    {
        currentEdges += static_cast< int >( adjacency.size() );
    }

    currentEdges /= 2;
    complementEdges = maxEdges - currentEdges;

    return complementEdges;
}

void Graph::depthSearch( int v, Vector< bool >& visited )
{
    visited[ v ] = true;

    for( int u : adjacency_list[ v ] )
    {
        if( !visited[ u ] )
        {
            depthSearch( u, visited );
        }
    }
}

void readInput( Vector< Graph >& graphs )
{
    const int adjustIndexToArray = 1;

    int numberOfGraphs = 0;
    std::cin >> numberOfGraphs;
    std::cin.ignore();

    for( int i = 0; i < numberOfGraphs; ++i )
    {
        int numberOfVertices = 0;
        std::cin >> numberOfVertices;
        std::cin.ignore();

        Graph g( numberOfVertices );
        for( int j = 0; j < numberOfVertices; j++ )
        {
            String line;
            readLine( std::cin, line );
            std::stringstream ss( line.c_str() );

            int number;
            ss >> number;

            Adjacency adj;
            while( ss >> number )
            {
                adj.push_back( number - adjustIndexToArray );
            }
            g.addEdge( j, adj );
        }
        graphs.push_back( g );
    }
}

int main()
{
    Vector< Graph > graphs;
    readInput( graphs );

    for( auto& g : graphs )
    {
        Vector< int > degrees = g.degreeSequence();
        std::sort( degrees.begin(), degrees.end(), std::greater<>() );
        for( const int d : degrees )
        {
            std::cout << d << "";
        }
        std::cout << '\n';

        int components = g.countComponents();
        std::cout << components;
        std::cout << '\n';

        char bipartite = g.isBipartite();
        std::cout << bipartite;
        std::cout << '\n';

        Vector< int > eccentricities = g.eccentricity();
        for( const int e : eccentricities )
        {
            std::cout << e << "";
        }
        std::cout << '\n';

        std::cout << '?';
        std::cout << '\n';

        Vector< int > greedyColours = g.greedyColoring();
        for( const int gc : greedyColours )
        {
            std::cout << gc << "";
        }
        std::cout << '\n';

        Vector< int > lfColours = g.lfColoring();
        for( const int lf : lfColours )
        {
            std::cout << lf << "";
        }
        std::cout << '\n';

        std::cout << '?';
        std::cout << '\n';

        std::cout << '?';
        std::cout << '\n';

        int complementEdges = g.countComplementsEdges();
        std::cout << complementEdges;
        std::cout << '\n';
    }

    return 0;
}