Теория графов в Игре Престолов

#ifndef DEF_H
#define DEF_H
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <set>
#include <iterator>
#include <functional>

using namespace std;

extern int reverseID[];
extern vector<int> id;
extern vector< vector<int> > weight, edge;
extern map<int, string> name;
extern int V, E;

void read_data();
#endif

#include "definitions.h"

int reverseID[3000];
vector<int> id; // origin ID of characters
vector< vector<int> > weight; // weights of edges
vector< vector<int> > edge; // the graph's edges
map<int, string> name; // names of characters
int V, E; // amount of vertices and edges

void read_data() {
    freopen("input.in", "r", stdin); // read from the input file

    cin >> V >> E;
  
    id.resize(V);
    weight.resize(V);
    edge.resize(V);

    int u;
    char s[100];
    for (int i = 0; i < V; i++) { // read the names
        scanf("%d %[^n]", &u, s);
        name[i] = string(s);
        id[i] = u; // origin ID by assigned ID
        reverseID[u] = i; // assigned ID by origin ID
    }

    int a, b, w;
    for (int i = 0; i < E; i++) { // read the edges and weights
        cin >> a >> b >> w;
        edge[reverseID[a]].push_back(reverseID[b]);
        edge[reverseID[b]].push_back(reverseID[a]);
        weight[reverseID[a]].push_back(w);
        weight[reverseID[b]].push_back(w);
    }
}

#include "definitions.h"
#include "degree.h"
#include "dfsbfs.h"
#include "bridges_articulations.h"
#include "cliques.h"
#include "spanning.h"
#include "cut.h"

int main() {
    read_data();

    degree();
    count_components();
    calculate_diameter();
    find_cliques();
    get_spanning_tree();
    find_bridges_and_articulations();
    find_cut();
}

#include "definitions.h"

void degree() {
    freopen("degree.txt", "w", stdout); // output file

    vector< pair<int,int> > degree(V);
    for (int i = 0; i < V; i++) {
        degree[i] = make_pair(edge[i].size(), i);
    }

    stable_sort(degree.begin(), degree.end());

    for (int i = V-1; i >= 0; i--) {
        cout << name[degree[i].second] << ": " << degree[i].first << endl;
    }
}

#include "definitions.h"

vector<bool> useddfs;
vector<int> comp;

void dfs(int u) {
    useddfs[u] = true;
    comp.push_back(u);
    for (vector<int>::iterator i = edge[u].begin(); i != edge[u].end(); i++)
        if (!useddfs[*i])
            dfs(*i);
}

void count_components() {
    freopen("components.txt", "w", stdout); // output file

    int comp_num = 0;
    useddfs.resize(V, false);
    for (int i = 0; i < V; i++) {
        if (!useddfs[i]) {
            comp.clear();
            dfs(i);
            comp_num++;
        }
    }
    cout << comp_num;
}

#include "definitions.h"

vector<bool> usedbfs;

void bfs(int u, vector<int> &distance, vector<int> &path) {
    queue<int> q;
    q.push(u);
    usedbfs[u] = true;
    path[u] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (vector<int>::iterator i = edge[u].begin(); i != edge[u].end(); i++) {
            int to = *i;
            if (!usedbfs[to]) {
                usedbfs[to] = true;
                q.push(to);
                distance[to] = distance[u] + 1;
                path[to] = u;
            }
        }
    }
}

void calculate_diameter() {
    freopen("diameter.txt", "w", stdout); // output file

    int diameter = 0;
    int current_max = 0;
    double average_max = 0;
    double average_average = 0;
    vector< vector<int> > distribution(V, vector<int> (0));
    vector< vector<int> > max_path;
    vector<int> farthest_node;
    for (int i = 0; i < V; i++) {
        vector<int> distance_to(V, 0);
        vector<int> path(V,-1);
        usedbfs.clear();
        usedbfs.resize(V, false);
        bfs(i, distance_to, path);
        current_max = 0;
        for (int j = 0; j < V; j++) {
            average_average += distance_to[j];

            if (distance_to[j] > current_max)
                current_max = distance_to[j];

            if (distance_to[j] > diameter) {
                diameter = distance_to[j];
                farthest_node.clear();
                max_path.clear();
                max_path.push_back(path);
                farthest_node.push_back(j);
            } else if (distance_to[j] == diameter){
                max_path.push_back(path);
                farthest_node.push_back(j);
            }
        }
        average_max += current_max;
        distribution[current_max].push_back(i);
    }
    average_max /= V;
    average_average /= V*V;

    cout << "Diameter: " << diameter << endl;
    cout << "Average path: " << average_average << endl;
    cout << "Average farthest path: " << average_max << endl;

    vector < vector<int> > farthest_path;    

    for (int i = 0; i < farthest_node.size(); i++) {
        farthest_path.push_back(vector<int>());
        for (int u = farthest_node[i]; u != -1; u = max_path[i][u])
            farthest_path[i].push_back(u);
    }

    cout << "Farthest paths:" << endl;
    for (int i = 0; i < farthest_path.size(); i++) {
        cout << i+1 << ": ";
        for (vector<int>::iterator j = farthest_path[i].begin(); j != farthest_path[i].end(); j++)
            cout << name[*j] << ". ";
        cout << endl;
    }

    int minimum = V;
    cout << "Farthest paths distribution:" << endl;
    for (int i = 0; i <= diameter; i++) {
        if (distribution[i].size() != 0 && i < minimum)
            minimum = i;

        cout << i << ": " << distribution[i].size() << endl;
    }

    cout << "Characters with minimum farthest path:" << endl;
    for (vector<int>::iterator i = distribution[minimum].begin(); i != distribution[minimum].end(); i++) {
        cout << name[*i] << endl;
    }
}

#include "definitions.h"

vector < vector<int> > cliques;

bool compare_vectors_by_size(const vector<int> &i, const vector<int> &j)
{
    return (i.size() > j.size());
}

void bron_kerbosch(set <int> R, set <int> P, set <int> X) { // where R is probable clique, P - possible vertices in clique, X - exluded vertices
    if (P.size() == 0 && X.size() == 0) { // R is maximal clique
        cliques.push_back(vector<int>(0));
        for (set<int>::iterator i = R.begin(); i != R.end(); i++) {
            cliques.back().push_back(*i);
        }
    }
    else {
        set <int> foriterate = P;
        for (set<int>::iterator i = foriterate.begin(); i != foriterate.end(); i++) {
            set <int> newR;
            set <int> newP;
            set <int> newX;

            newR = R;
            newR.insert(*i);

            set_intersection(P.begin(), P.end(), edge[*i].begin(), edge[*i].end(), inserter(newP, newP.begin()));

            set_intersection(X.begin(), X.end(), edge[*i].begin(), edge[*i].end(), inserter(newX, newX.begin()));

            bron_kerbosch(newR, newP, newX);

            P.erase(*i);
            X.insert(*i);
        }
    }
}

void find_cliques() {
    freopen("cliques.txt", "w", stdout); // output file

    set <int> P;
    for (int i = 0; i < V; i++) {
        P.insert(i);
        stable_sort(edge[i].begin(), edge[i].end());
    }
    
    bron_kerbosch(set<int>(), P, set<int>());

    stable_sort(cliques.begin(), cliques.end(), compare_vectors_by_size);

    cout << "Distribution:" << endl;
    int max_size = 0;
    int max_counter = 0;
    for (int i = cliques.size()-1; i >= 0 ; i--) {
        if (cliques[i].size() > max_size) {
            if (max_counter > 0) {
                cout << max_size << ": " << max_counter << endl;
            }
            max_size = cliques[i].size();
            max_counter = 0;
        }

        max_counter++;
    }
    if (max_counter > 0) {
        cout << max_size << ": " << max_counter << endl;
    }

    cout << "Cliques:" << endl;
    for (int i = 0; i < cliques.size(); i++) {
        cout << i + 1 << "(" << cliques[i].size() << "): ";
        for (int j = 0; j < cliques[i].size(); j++) {
            cout << name[cliques[i][j]] << ". ";
        }
        cout << endl;
    }
}

#include "definitions.h"

vector<int> p;

int dsu_get(int v) {
    return (v == p[v]) ? v : (p[v] = dsu_get(p[v]));
}

void dsu_unite(int u, int v) {
    u = dsu_get(u);
    v = dsu_get(v);

    if (rand() & 1)
        swap(u, v);

    if (u != v)
        p[u] = v;
}


void get_spanning_tree() {
    freopen("spanning.txt", "w", stdout); // output file

    vector < pair < int, pair<int, int> > > edges_weights, result;

    vector < vector<bool> > used;
    for (int i = 0; i < V; i++) {
        used.push_back(vector<bool>(V, false));
    }

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < edge[i].size(); j++) {
            int cur_v = edge[i][j];
            if (!used[i][cur_v]) {
                edges_weights.push_back(make_pair(weight[i][j], make_pair(i, cur_v)));
                used[i][cur_v] = true;
                used[cur_v][i] = true;
            }
        }
    }

    sort(edges_weights.begin(), edges_weights.end(), greater< pair < int, pair<int, int> > >());

    for (int i = 0; i < V; i++) {
        p.push_back(i);
    }

    for (int i = 0; i < E; i++) {
        int u = edges_weights[i].second.first;
        int v = edges_weights[i].second.second;
        int w = edges_weights[i].first;

        if (dsu_get(u) != dsu_get(v)) {
            result.push_back(edges_weights[i]);
            dsu_unite(u, v);
        }
    }

    for (vector < pair < int, pair<int, int> > >::iterator i = result.begin(); i != result.end(); i++) {
        cout << id[(i->second).first] << " " << id[(i->second).second] << " " << i->first << endl;
    }
}

#include "definitions.h"

vector<bool> used, usedcnt;
int timer = 0;
vector<int> tin, fout, articulations;
vector < pair<int,int> > bridges;

int count_rec(int v, int skip) {
    int cnt = 1;
    usedcnt[v] = true;

    for (int i = 0; i < edge[v].size(); i++) {
        int to = edge[v][i];

        if(to == skip || usedcnt[to]) 
            continue;

        cnt += count_rec(to, skip);
    }
    
    return cnt;
}

int count_from(int v, int skip, bool clean = true){
    usedcnt.resize(V, false);

    if (clean) {
        for (int i = 0; i < usedcnt.size(); i++)
            usedcnt[i] = false;
    }
         
    return count_rec(v, skip);
}

void dfs(int v, int prev = -1) {
    used[v] = true;
    tin[v] = fout[v] = timer++;

    int root_calls = 0;
    bool in_ar_list = false;
    for (int i = 0; i < edge[v].size(); i++) {
        int to = edge[v][i];

        if (to == prev)  continue;

        if (used[to])
            fout[v] = min(fout[v], tin[to]);
        else {
            dfs(to, v);
            fout[v] = min(fout[v], fout[to]);

            if (fout[to] > tin[v]) {
                bridges.push_back(make_pair(v, to));
            }
            
            if (fout[to] >= tin[v] && prev != -1 && !in_ar_list) {
                articulations.push_back(v);
                in_ar_list = true;
            }
            
            root_calls++;
        }
    }
    
	if (prev == -1 && root_calls > 1)
		articulations.push_back(v);
}

void find_bridges_and_articulations() {
    freopen("bridges_and_articulations.txt", "w", stdout); // output file

    used.resize(V, false);
    tin.resize(V);
    fout.resize(V);

    for (int i = 0; i < V; i++)
        if (!used[i])
            dfs(i);
    
    cout << "Bridges:" << endl;
    for (int i = 0; i < bridges.size(); i++) {
        cout << name[bridges[i].first] << " (" << count_from(bridges[i].first, bridges[i].second) << ") - " << name[bridges[i].second] << " (" << count_from(bridges[i].second, bridges[i].first) <<")" << endl;
    }
    
    
    cout << endl << "Articulation points:" << endl;  
    for (int i = 0; i < articulations.size(); i++) {
        int cur = articulations[i];
        cout << name[cur];
        
        for (int i = 0; i < usedcnt.size(); i++)
            usedcnt[i] = false;
            
        for (int j = 0; j < edge[cur].size(); j++) {
            if (!usedcnt[edge[cur][j]]) {
                int comp_size = count_from(edge[cur][j], cur, false); 
                cout << " (" << comp_size << ")";
            }
        }
        cout << endl;
    }
}

#include "definitions.h"

const int INF = 1000000000;

struct edge_s{
    int a, b, c, flow; // a->b, c-capacity, flow=0
    edge_s(int a, int b, int c, int flow) : a(a), b(b), c(c), flow(flow) {}
};

vector< pair<int, int> > top_degree;
vector< pair<int, int> > top_flow;
vector<int> dis;
vector<int> ptr;
vector<edge_s> edgelist;
vector< vector<int> > edges_dup;

bool compare_pairs_by_second(const pair<int, int> &i, const pair<int, int> &j)
{
    return (i.second > j.second);
}

bool bfs_dinic(int s, int t) {
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    
    while (!q.empty() && dis[t] == -1) {
        int v = q.front();
        q.pop();
        
        for (int i = 0; i < edges_dup[v].size(); i++) {
            int ind = edges_dup[v][i],
            next = edgelist[ind].b;
            
            if (dis[next] == -1 && edgelist[ind].flow < edgelist[ind].c) {
                q.push(next);
                dis[next] = dis[v] + 1;
            }
        }
    }
    
    return dis[t] != -1;
}

int dfs_dinic(int v, int t, int flow) {
    if (!flow) {
        return 0;
    }
    
    if (v == t) {
        return flow;
    }
    
    for (; ptr[v] < (int) edges_dup[v].size(); ptr[v]++) {
        int ind = edges_dup[v][ptr[v]];
        int next = edgelist[ind].b;
        
        if (dis[next] != dis[v] + 1) {
            continue;
        }
        
        int pushed = dfs_dinic(next, t, min(flow, edgelist[ind].c - edgelist[ind].flow));
        
        if (pushed) {
            edgelist[ind].flow += pushed;
            edgelist[ind ^ 1].flow -= pushed;
            return pushed;
        }
    }
    
    return 0;
}

long long dinic_flow(int s, int t) {
    long long flow = 0;
     
    while (true) {
        fill(dis.begin(), dis.end(), -1);
        
        if (!bfs_dinic(s, t)) {
            break;
        }
        
        fill(ptr.begin(), ptr.end(), 0);
        
        while (int pushed = dfs_dinic(s, t, INF)) {
            flow += pushed;
        }
    }
    return flow;
}

void dinic_addedge(int a, int b, int c) {
    edges_dup[a].push_back((int) edgelist.size());
    edgelist.push_back(edge_s(a, b, c, 0));
    edges_dup[b].push_back((int) edgelist.size());
    edgelist.push_back(edge_s(b, a, 0, 0));
}

void find_cut() {
    freopen("cut_min.txt", "w", stdout); // output file
    
    dis.resize(2 * V, 0);
    ptr.resize(2 * V, 0);
    edges_dup.resize(2 * V, vector<int>(0));
    const int top = min(10, V);

    for (int i = 0; i < V; i++)
        top_flow.push_back(make_pair(0, i));

    for (int i = 0; i < V; i++) {
        top_degree.push_back(make_pair(edge[i].size(), i));
        for (int j = 0; j < edge[i].size(); j++) {
            int to = edge[i][j];
            dinic_addedge(i, to + V, V);
        }
        dinic_addedge(i + V, i, 1);
    }
    
    stable_sort(top_degree.rbegin(), top_degree.rend());
    
    cout << "Minimum cut between characters:" << endl;
    for (int i = 0; i < top; i++) {
        for (int j = i + 1; j < top; j++) {
            vector<int>::iterator p = find(edge[top_degree[i].second].begin(), edge[top_degree[i].second].end(), top_degree[j].second);
            
            if (p != edge[top_degree[i].second].end())
                continue;
            
            int flow = dinic_flow(top_degree[i].second, top_degree[j].second + V);
            cout << name[top_degree[i].second] << " -> " << name[top_degree[j].second] << " = " << flow << endl;     

            for (int k = 0; k < edgelist.size(); k++) {
                if ((edgelist[k].a == (edgelist[k].b + V)) && (edgelist[k].flow == 1)) {
                    top_flow[edgelist[k].b].first++;
                }
                edgelist[k].flow = 0;
            }
        }
    }
    
    stable_sort(top_flow.rbegin(), top_flow.rend());

    cout << endl << "Top involved characters in the flows:" << endl;
    for (int i = 0; i < top; i++) {
        cout << name[top_flow[i].second] << " (" << top_flow[i].first << ")" << endl;
    }
}