Untitled
unknown
c_cpp
a year ago
19 kB
5
Indexable
#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; }
Editor is loading...
Leave a Comment