nvim/snippets/c/acm/Class_Graph.code-snippets

{
	"Graph": {
		"prefix": "Class_Graph",
		"body": [
			"",
			"template <class T>",
			"class Graph {",
			" public:",
			"  struct edge {",
			"    int next, to;",
			"    T w;",
			"  };",
			"  int n;",
			"  vector<vector<T>> maps;",
			"  vector<T> dis;",
			"  vector<edge> e;",
			"  vi head, bj;",
			"  Graph() {}",
			"",
			"  Graph(int n) {",
			"    this->n = n, this->m = n * (n - 1);",
			"    head = vi(n + 1, -1), e = vector<edge>(m * 2 + 1);",
			"  }",
			"",
			"  Graph(int n, int m) {",
			"    this->n = n, this->m = m, head = vi(n + 1, -1), e = vector<edge>(m * 2 + 1);",
			"  }",
			"",
			"  void add(int u, int v, T w) {",
			"    e[cnt].to = v, e[cnt].next = head[u], e[cnt].w = w, head[u] = cnt++;",
			"  }",
			"",
			"  void add(int u, int v) {",
			"    e[cnt].to = v, e[cnt].next = head[u], head[u] = cnt++;",
			"  }",
			"",
			" private:",
			"  int m, cnt = 0;",
			"};",
			"#define e g.e",
			"#define head g.head",
			"#define maps g.maps",
			"#define add g.add",
			""
		]
	},
	"Class_Graph_Dijkstra": {
		"prefix": "Class_Graph_Dijkstra",
		"body": [
			"",
			"#define dis g.dis",
			"#define bj g.bj",
			"ll dijkstra(Graph<ll> g, int st, int en) {",
			"  dis = vll(g.n + 1, inf),",
			"  bj = vi(g.n + 1);",
			"  priority_queue<pll, vector<pll>, greater<pll>> q;",
			"  dis[st] = 0;",
			"  q.push({0, st});",
			"  while (!q.empty()) {",
			"    int u = q.top().y;",
			"    q.pop();",
			"    if (bj[u]) continue;",
			"    bj[u] = 1;",
			"    for (int i = head[u]; ~i; i = e[i].next) {",
			"      int v = e[i].to;",
			"      if (dis[v] > dis[u] + e[i].w) {",
			"        dis[v] = dis[u] + e[i].w;",
			"        q.push({dis[v], v});",
			"      }",
			"    }",
			"  }",
			"  if (dis[en] != inf)",
			"    return dis[en];",
			"  else",
			"    return -1;",
			"}",
			""
		]
	},
	"Class_Graph_SPFA": {
		"prefix": "Class_Graph_SPFA",
		"body": [
			"",
			"ll spfa(Graph<ll> g, int st, int en) {",
			"  vll bj(g.n + 1), dis(g.n + 1, inf), num(g.n + 1);",
			"  queue<int> q;",
			"  dis[st] = 0;",
			"  bj[st] = 1;",
			"  q.push(st);",
			"  while (q.size()) {",
			"    int u = q.front();",
			"    if (!bj[u]) continue;",
			"    if (num[u] > g.n + 1) return inf;//判断是否产生负环",
			"    bj[u] = 0, num[u]++;",
			"    for (int i = head[u]; ~i; i = e[i].next) {",
			"      int w = e[i].w, v = e[i].to;",
			"      if (dis[v] > dis[u] + w) {",
			"        dis[v] = dis[u] + w;",
			"        if (!bj[v]) q.push(v);",
			"      }",
			"    }",
			"  }",
			"  if(dis[en] == inf) return -1;",
			"  return dis[en];",
			"}",
			""
		]
	},
	"Class_Graph_Kurskal": {
		"prefix": "Class_Graph_Kurskal",
		"body": [
			"",
			"ll kruskal(Graph<ll> g, Dsu d) {",
			"  ll res = 0, cnt = 0;",
			"  sort(e.begin(), e.end());",
			"  for (auto i : e) {",
			"    int u = i.u, v = i.v, w = i.w;",
			"    int q = d.find(i.u), p = d.find(i.v);",
			"    if (d.Dunion(q, p)) cnt++, res += w;",
			"    if (cnt == n - 1) break;",
			"  }",
			"  return res;",
			"}",
			""
		]
	},
	"Class_Graph_Prim": {
		"prefix": "Class_Graph_Prim",
		"body": []
	},
	"Class_Graph_TreeDiam": {
		"prefix": "Class_Graph_TreeDiam",
		"description": "树的直径",
		"body": [
			"ll TreeDiam(Graph<ll> g) {",
			"  vll dis1(n + 1), dis2(n + 1), p(n + 1), up(n + 1);",
			"  function<ll(ll, ll)> dfs = [&](ll u, ll fa) {",
			"    for (int i = head[u]; ~i; i = e[i].next) {",
			"      int v = e[i].to, w = 1;",
			"      if (v == fa) continue;",
			"      ll x = dfs(v, u) + 1;",
			"      if (x >= dis1[u])",
			"        dis2[u] = dis1[u], dis1[u] = x, p[u] = v;",
			"      else if (x >= dis2[u])",
			"        dis2[u] = x;",
			"    }",
			"    return dis1[u];",
			"  };",
			"  function<void(ll, ll)> dfs0 = [&](ll u, ll fa) {",
			"    for (int i = head[u]; ~i; i = e[i].next) {",
			"      int v = e[i].to, w = 1;",
			"      if (v == fa) continue;",
			"      if (p[u] == v)",
			"        up[v] = max(dis2[u], up[u]) + w;",
			"      else",
			"        up[v] = max(dis1[u], up[u]) + w;",
			"      dfs0(v, u);",
			"    }",
			"  };",
			"  dfs(1, -1), dfs0(1, -1);",
			"  ll ans = -1;",
			"  for (int i = 1; i <= n + m; i++) {",
			"    if (dis1[i] == dis2[i] && dis1[i] == 0)",
			"      ans = max(ans, up[i]);",
			"    else",
			"      ans = max(ans, max(up[i], dis1[i]));",
			"  }",
			"  return ans;",
			"}"
		]
	},
	"Class_Graph_SCC": {
		"prefix": "Class_Graph_SCC",
		"body": [
			"",
			"class SCC {",
			" public:",
			"  stack<ll> stk;",
			"  int timestamp = 0, scc_cnt = 0, n, m;",
			"  vll dfn, low, in_stk, Size, id;",
			"  Graph<ll> g;",
			"",
			"  SCC() {}",
			"",
			"  SCC(Graph<ll> g) {",
			"    this->n = g.n, this->m = g.m, this->g = g;",
			"    dfn = vll(n + 1, 0);",
			"    low = vll(n + 1, 0);",
			"    in_stk = vll(n + 1, 0);",
			"    Size = vll(n + 1, 0);",
			"    id = vll(n + 1, 0);",
			"    for (int i = 1; i <= n; i++)",
			"      if (!dfn[i]) tarjan(i);",
			"  }",
			"",
			"  void tarjan(int u) {",
			"    dfn[u] = low[u] = ++timestamp;",
			"    stk.push(u), in_stk[u] = 1;",
			"    for (int i = head[u]; ~i; i = e[i].next) {",
			"      int v = e[i].to;",
			"      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 (low[u] == dfn[u]) {",
			"      ++scc_cnt;",
			"      int v;",
			"      do {",
			"        v = stk.top();",
			"        stk.pop();",
			"        in_stk[v] = 0;",
			"        id[v] = scc_cnt;",
			"        Size[scc_cnt]++;",
			"      } while (v != u);",
			"    }",
			"    return;",
			"  }",
			"};",
			""
		]
	},
	"Class_Graph_Euler": {
		"prefix": "Class_Graph_Euler",
		"body": [
			"",
			"vll din, dout;",
			"",
			"class Euler {",
			"  public:",
			"  int n, m;",
			"  Graph<ll> g;",
			"  vector<bool> used;",
			"  vll path;",
			"  Euler() {}",
			"  Euler(Graph<ll> g) {",
			"    this->n = g.n, this->m = g.m, this->g = g;",
			"    used = vector<bool>(n + 1);",
			"  }",
			"",
			"  void dfs_u(int u) {",
			"    //无向图",
			"    for (long long &i  = head[u]; i; i = e[i].next) {",
			"      long long j = i & 1 ? i + 1 : i - 1;",
			"      if(used[i]) {",
			"        i = e[i].next;",
			"        continue;",
			"      }",
			"      used[j] = used[i] = true;",
			"      int t = i / 2 + 1;",
			"      dfs_u(e[i].to);",
			"      path.push_back(t);",
			"    }",
			"  }",
			"",
			"  void dfs_o(int u) {",
			"    // 有向图",
			"    for (long long &i  = head[u]; i; i = e[i].next) {",
			"      if(used[i]) {",
			"        i = e[i].next;",
			"        continue;",
			"      }",
			"      used[i] = true;",
			"      int t = i + 1;",
			"      dfs_o(e[i].to);",
			"      path.push_back(t);",
			"    }",
			"  }",
			"",
			"};",
			"#define path eu.path",
			""
		]
	},
	"Class_Graph_LCA": {
		"prefix": "Class_Graph_LCA",
		"body": [
			"",
			"class LCA {",
			" public:",
			"  int n;",
			"  vll depth, fa[33];",
			"",
			"  LCA() {}",
			"  LCA(Graph<ll> g, int root) {",
			"    n = g.n, depth = vll(n + 1, inf);",
			"    for (int i = 0; i <= 32; i++) fa[i] = vll(n + 1);",
			"    bfs(g, root);",
			"  }",
			"",
			"  void bfs(Graph<ll> g, int root) {",
			"    depth[0] = 0, depth[root] = 1;",
			"    queue<int> q;",
			"    q.push(root);",
			"    while (q.size()) {",
			"      auto u = q.front();",
			"      q.pop();",
			"      for (int i = head[u]; ~i; i = e[i].next) {",
			"        int v = e[i].to;",
			"        if (depth[v] > depth[u] + 1) {",
			"          depth[v] = depth[u] + 1;",
			"          q.push(v);",
			"          fa[0][v] = u;",
			"          for (int k = 1; k <= 32; k++) fa[k][v] = fa[k - 1][fa[k - 1][v]];",
			"        }",
			"      }",
			"    }",
			"  }",
			"",
			"  int query(int a, int b) {",
			"    if (depth[a] < depth[b]) swap(a, b);",
			"    for (int i = 32; i >= 0; i--)",
			"      if (depth[fa[i][a]] >= depth[b]) a = fa[i][a];",
			"    if (a == b) return a;",
			"    for (int i = 32; i >= 0; i--)",
			"      if (fa[i][a] != fa[i][b]) a = fa[i][a], b = fa[i][b];",
			"    return fa[0][a];",
			"  }",
			"};",
			""
		]
	},
	"Class_Graph_erfen": {
		"prefix": "Class_Graph_erfen",
		"body": [
			"",
			"class erfen_graph {",
			" public:",
			"  ll res, n;",
			"  vi match, st;",
			"  Graph<ll> g;",
			"  erfen_graph(Graph<ll> g) {",
			"    this->g = g, this->n = g.n;",
			"    st = vector<int>(n + 1), match = vector<int>(n + 1);",
			"    res = 0;",
			"    for (int i = 1; i <= n; i++) {",
			"      st = vector<int>(n + 1);",
			"      if (find(i)) res++;",
			"    }",
			"  }",
			"",
			"  bool find(int u) {",
			"    for (int i = head[u]; ~i; i = e[i].next) {",
			"      if (!st[e[i].to]) {",
			"        st[e[i].to] = true;",
			"        if (!match[e[i].to] || find(match[e[i].to])) {",
			"          match[e[i].to] = u;",
			"          return true;",
			"        }",
			"      }",
			"    }",
			"    return false;",
			"  }",
			"};",
			""
		]
	}
}