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