main.cpp - master - Leonid174/dm_encoding_graphs

main.cpp
423 строки13 KB
Leonid174
create: output_chain.txt, input_1e3_1e5 (1).txt, main.cpp
16 май 2026, 18:18
16 май 2026, 18:181a58004
#include <climits>
#include <fstream>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

class Graph {
private:
    int n;
    int m;
    int directed;
    int weighted;
    int repr;

    vector<vector<int>> adjMatrix;
    vector<set<pair<int, int>>> adjList;
    vector<tuple<int, int, int>> edgeList;

public:
    Graph() : n(0), m(0), directed(0), weighted(0), repr(0) {}

    void readGraph(string fileName) {
        ifstream in(fileName);
        char type;
        in >> type;
        if (type == 'C') {
            in >> n;
            in >> directed >> weighted;
            repr = 1;
            adjMatrix.assign(n + 1, vector<int>(n + 1, 0));
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    in >> adjMatrix[i][j];
                }
            }
            m = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (adjMatrix[i][j] != 0) {
                        if (directed || i < j) {
                            m++;
                        }
                    }
                }
            }
        }
        else if (type == 'L') {
            in >> n;
            in >> directed >> weighted;
            repr = 2;
            adjList.assign(n + 1, set<pair<int, int>>());
            string line;
            getline(in, line);
            for (int i = 1; i <= n; i++) {
                getline(in, line);
                if (!line.empty() && line.back() == '\r') {
                    line.pop_back();
                }
                stringstream ss(line);
                if (weighted) {
                    int v, w;
                    while (ss >> v >> w) {
                        adjList[i].insert({ v, w });
                    }
                }
                else {
                    int v;
                    while (ss >> v) {
                        adjList[i].insert({ v, 1 });
                    }
                }
            }
            m = 0;
            for (int i = 1; i <= n; i++) {
                m += adjList[i].size();
            }
            if (!directed) {
                m /= 2;
            }
        }
        else if (type == 'E') {
            in >> n >> m;
            in >> directed >> weighted;
            repr = 3;
            edgeList.clear();
            for (int i = 0; i < m; i++) {
                int a, b, w = 1;
                if (weighted) {
                    in >> a >> b >> w;
                }
                else {
                    in >> a >> b;
                }
                edgeList.push_back(make_tuple(a, b, w));
            }
        }
        in.close();
    }

    void addEdge(int from, int to, int weight) {
        if (repr == 1) {
            bool wasEdge = (adjMatrix[from][to] != 0);
            adjMatrix[from][to] = weight;
            if (!directed) {
                adjMatrix[to][from] = weight;
            }
            if (!wasEdge) {
                m++;
            }
        }
        else if (repr == 2) {
            auto it = adjList[from].lower_bound({ to, INT_MIN });
            bool wasEdge = (it != adjList[from].end() && it->first == to);
            if (wasEdge) {
                adjList[from].erase(it);
            }
            adjList[from].insert({ to, weight });
            if (!directed) {
                auto it2 = adjList[to].lower_bound({ from, INT_MIN });
                if (it2 != adjList[to].end() && it2->first == from) {
                    adjList[to].erase(it2);
                }
                adjList[to].insert({ from, weight });
            }
            if (!wasEdge) {
                m++;
            }
        }
        else if (repr == 3) {
            bool found = false;
            for (auto& e : edgeList) {
                int a = get<0>(e);
                int b = get<1>(e);
                if (a == from && b == to) {
                    get<2>(e) = weight;
                    found = true;
                    break;
                }
                if (!directed && a == to && b == from) {
                    get<2>(e) = weight;
                    found = true;
                    break;
                }
            }
            if (!found) {
                edgeList.push_back(make_tuple(from, to, weight));
                m++;
            }
        }
    }

    void removeEdge(int from, int to) {
        if (repr == 1) {
            bool wasEdge = (adjMatrix[from][to] != 0);
            adjMatrix[from][to] = 0;
            if (!directed) {
                adjMatrix[to][from] = 0;
            }
            if (wasEdge) {
                m--;
            }
        }
        else if (repr == 2) {
            auto it = adjList[from].lower_bound({ to, INT_MIN });
            bool wasEdge = (it != adjList[from].end() && it->first == to);
            if (wasEdge) {
                adjList[from].erase(it);
            }
            if (!directed) {
                auto it2 = adjList[to].lower_bound({ from, INT_MIN });
                if (it2 != adjList[to].end() && it2->first == from) {
                    adjList[to].erase(it2);
                }
            }
            if (wasEdge) {
                m--;
            }
        }
        else if (repr == 3) {
            for (auto it = edgeList.begin(); it != edgeList.end(); ++it) {
                int a = get<0>(*it);
                int b = get<1>(*it);
                if (a == from && b == to) {
                    edgeList.erase(it);
                    m--;
                    break;
                }
                if (!directed && a == to && b == from) {
                    edgeList.erase(it);
                    m--;
                    break;
                }
            }
        }
    }

    int changeEdge(int from, int to, int newWeight) {
        int oldWeight = 0;
        if (repr == 1) {
            oldWeight = adjMatrix[from][to];
            adjMatrix[from][to] = newWeight;
            if (!directed) {
                adjMatrix[to][from] = newWeight;
            }
        }
        else if (repr == 2) {
            auto it = adjList[from].lower_bound({ to, INT_MIN });
            if (it != adjList[from].end() && it->first == to) {
                oldWeight = it->second;
                adjList[from].erase(it);
                adjList[from].insert({ to, newWeight });
            }
            if (!directed) {
                auto it2 = adjList[to].lower_bound({ from, INT_MIN });
                if (it2 != adjList[to].end() && it2->first == from) {
                    adjList[to].erase(it2);
                    adjList[to].insert({ from, newWeight });
                }
            }
        }
        else if (repr == 3) {
            for (auto& e : edgeList) {
                int a = get<0>(e);
                int b = get<1>(e);
                if (a == from && b == to) {
                    oldWeight = get<2>(e);
                    get<2>(e) = newWeight;
                    break;
                }
                if (!directed && a == to && b == from) {
                    oldWeight = get<2>(e);
                    get<2>(e) = newWeight;
                    break;
                }
            }
        }
        return oldWeight;
    }

    void transformToAdjList() {
        if (repr == 2) {
            return;
        }
        adjList.assign(n + 1, set<pair<int, int>>());
        if (repr == 1) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (adjMatrix[i][j] != 0) {
                        adjList[i].insert({ j, adjMatrix[i][j] });
                    }
                }
            }
        }
        else if (repr == 3) {
            for (const auto& e : edgeList) {
                int a = get<0>(e);
                int b = get<1>(e);
                int w = get<2>(e);
                adjList[a].insert({ b, w });
                if (!directed) {
                    adjList[b].insert({ a, w });
                }
            }
        }
        repr = 2;
        adjMatrix.clear();
        adjMatrix.shrink_to_fit();
        edgeList.clear();
        edgeList.shrink_to_fit();
    }

    void transformToAdjMatrix() {
        if (repr == 1) {
            return;
        }
        adjMatrix.assign(n + 1, vector<int>(n + 1, 0));
        if (repr == 2) {
            for (int i = 1; i <= n; i++) {
                for (const auto& p : adjList[i]) {
                    adjMatrix[i][p.first] = p.second;
                }
            }
        }
        else if (repr == 3) {
            for (const auto& e : edgeList) {
                int a = get<0>(e);
                int b = get<1>(e);
                int w = get<2>(e);
                adjMatrix[a][b] = w;
                if (!directed) {
                    adjMatrix[b][a] = w;
                }
            }
        }
        repr = 1;
        adjList.clear();
        adjList.shrink_to_fit();
        edgeList.clear();
        edgeList.shrink_to_fit();
    }

    void transformToListOfEdges() {
        if (repr == 3) {
            return;
        }
        edgeList.clear();
        if (repr == 1) {
            if (directed) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (adjMatrix[i][j] != 0) {
                            edgeList.push_back(make_tuple(i, j, adjMatrix[i][j]));
                        }
                    }
                }
            }
            else {
                for (int i = 1; i <= n; i++) {
                    for (int j = i + 1; j <= n; j++) {
                        if (adjMatrix[i][j] != 0) {
                            edgeList.push_back(make_tuple(i, j, adjMatrix[i][j]));
                        }
                    }
                }
            }
        }
        else if (repr == 2) {
            if (directed) {
                for (int i = 1; i <= n; i++) {
                    for (const auto& p : adjList[i]) {
                        edgeList.push_back(make_tuple(i, p.first, p.second));
                    }
                }
            }
            else {
                for (int i = 1; i <= n; i++) {
                    for (const auto& p : adjList[i]) {
                        if (i < p.first) {
                            edgeList.push_back(make_tuple(i, p.first, p.second));
                        }
                    }
                }
            }
        }
        m = edgeList.size();
        repr = 3;
        adjMatrix.clear();
        adjMatrix.shrink_to_fit();
        adjList.clear();
        adjList.shrink_to_fit();
    }

    void writeGraph(string fileName) {
        ofstream out(fileName);
        if (repr == 1) {
            out << "C " << n << "\n";
            out << directed << " " << weighted << "\n";
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (j > 1) {
                        out << " ";
                    }
                    out << adjMatrix[i][j];
                }
                out << "\n";
            }
        }
        else if (repr == 2) {
            out << "L " << n << "\n";
            out << directed << " " << weighted << "\n";
            for (int i = 1; i <= n; i++) {
                bool first = true;
                for (const auto& p : adjList[i]) {
                    if (!first) {
                        out << " ";
                    }
                    first = false;
                    if (weighted) {
                        out << p.first << " " << p.second;
                    }
                    else {
                        out << p.first;
                    }
                }
                out << "\n";
            }
        }
        else if (repr == 3) {
            out << "E " << n << " " << m << "\n";
            out << directed << " " << weighted << "\n";
            for (const auto& e : edgeList) {
                int a = get<0>(e);
                int b = get<1>(e);
                int w = get<2>(e);
                if (weighted) {
                    out << a << " " << b << " " << w << "\n";
                }
                else {
                    out << a << " " << b << "\n";
                }
            }
        }
        out.close();
    }
};

int main() {
    Graph g;

    g.readGraph("input_1e3_1e5 (1).txt");

    g.transformToAdjList();
    g.transformToAdjMatrix();
    g.transformToListOfEdges();

    g.writeGraph("output_chain.txt");

    return 0;
}