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;
};

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;
}