Complete Graph Template

gt.cpp

#include <bits/stdc++.h>
#define ll long long
#define FASTIO   \
  cin.tie(NULL); \
  ios::sync_with_stdio(false);
#define END return 0;
#define out cout <<
#define in cin >>
using namespace std;

struct DirectedGraph {
  int n;
  vector<vector<int>> adj;
  vector<int> dfn, low, scc_id;
  vector<bool> in_stk;
  stack<int> stk;
  int dfs_cnt = 0, scc_cnt = 0;
  vector<vector<int>> sccs;
  DirectedGraph(int n) : n(n), adj(n), dfn(n), low(n), scc_id(n), in_stk(n) {}
  void add_edge(int u, int v) { adj[u].push_back(v); }
  void tarjan(int u) {
    dfn[u] = low[u] = ++dfs_cnt;
    stk.push(u);
    in_stk[u] = true;
    for (int v : adj[u]) {
      if (!dfn[v]) {
        tarjan(v);
        low[u] = min(low[u], low[v]);
      } else if (in_stk[v]) {
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (dfn[u] == low[u]) {
      vector<int> temp;
      while (true) {
        int v = stk.top();
        stk.pop();
        in_stk[v] = false;
        scc_id[v] = scc_cnt;
        temp.push_back(v);
        if (v == u) break;
      }
      sccs.push_back(temp);
      scc_cnt++;
    }
  }
  void build_scc() {
    for (int i = 0; i < n; i++)
      if (!dfn[i]) tarjan(i);
  }
  void bfs(int start, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
  }
  void dfs(int start, vector<bool>& visited) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
      int current = st.top();
      st.pop();
      if (visited[current]) continue;
      visited[current] = true;
      for (int v : adj[current]) {
        if (!visited[v]) st.push(v);
      }
    }
  }
};
struct UndirectedGraph {
  int n;
  vector<vector<int>> adj;
  UndirectedGraph(int n) : n(n), adj(n) {};
  void add_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  void bfs(int start, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
  }
  void dfs(int start, vector<bool>& visited) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
      int current = st.top();
      st.pop();
      if (visited[current]) continue;
      visited[current] = true;
      for (int v : adj[current]) {
        if (!visited[v]) st.push(v);
      }
    }
  }
};

// FOR KRUSKAL
struct Edge {
  int u, v, w;
  bool operator<(const Edge& other) const { return w < other.w; }
};

struct WeightedUndirectedGraph {
  int n;
  vector<vector<pair<int, int>>> adj;
  vector<Edge> edges;
  WeightedUndirectedGraph(int n) : n(n), adj(n) {};
  void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    edges.push_back({u, v, w});
  }
  void bfs(int start, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto& [v, w] : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
  }
  void dfs(int start, vector<bool>& visited) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
      int current = st.top();
      st.pop();
      if (visited[current]) continue;
      visited[current] = true;
      for (auto& [v, w] : adj[current]) {
        if (!visited[v]) st.push(v);
      }
    }
  }
  vector<ll> dijkstra(int start) {
    const ll INF = 1e18;
    vector<ll> dist(n, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (d > dist[u]) continue;
      for (auto& [v, w] : adj[u]) {
        if (dist[v] > dist[u] + w) {
          dist[v] = dist[u] + w;
          pq.push({dist[v], v});
        }
      }
    }
    return dist;
  }
  vector<Edge> kruskal(int n) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    vector<Edge> mst;
    for (Edge& e : edges) {
      if (uf.unite(e.u, e.v)) {
        mst.push_back(e);
      }
    }
    return mst;
  }
};

struct UnionFind {
  vector<int> parent, rank;
  UnionFind(int n) : parent(n), rank(n, 0) {
    iota(parent.begin(), parent.end(), 0);
  }
  int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) swap(x, y);
    parent[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
    return true;
  }
};

int main() {
  FASTIO

  END
}