C++での冗長接続
根なしの木が1つあるとします。これは、サイクルのない1つの無向グラフです。指定された入力は、N個のノード(ノードの値は1からNまでの範囲の個別の値)を持つツリーとして開始され、1つのエッジが追加されたグラフです。追加されたエッジには、1からNまで選択された2つの異なる頂点があり、既存のエッジではありませんでした。
最終的なグラフは、エッジの2D配列として示されます。エッジの各要素はペア[u、v]であり、ここでu
結果のグラフがNノードのツリーになるように、削除できるエッジを見つける必要があります。複数の答えがあるかもしれません、私たちは与えられた2Darrayで最後に起こる答えを見つけなければなりません。回答エッジ[u、v]は同じ形式で、u
したがって、入力が[[1,2]、[2,3]、[3,4]、[1,4]、[1,5]]、
のような場合
その場合、出力は[1,4]
になりますこれを解決するには、次の手順に従います-
-
N:=1000
-
サイズの親配列を定義します:N+5。
-
サイズの配列ランクを定義します:N+5。
-
関数getParent()を定義します。これにはnが必要です。
-
parent [n]が-1と同じ場合、-
-
nを返す
-
-
return parent [n] =getParent(parent [n])
-
関数unionn()を定義します。これには、a、b、
が必要です。 -
pa:=getParent(a)、pb:=getParent(b)
-
paがpbと同じ場合、-
-
falseを返す
-
-
ランク[pa]>ランク[pb]の場合、-
-
ランク[pa]:=ランク[pa]+ランク[pb]
-
親[pb]:=pa
-
-
それ以外の場合
-
ランク[pb]:=ランク[pb]+ランク[pa]
-
parent [pa]:=pb
-
-
trueを返す
-
メインの方法から、次のようにします-
-
n:=エッジリストのサイズ
-
初期化i:=0の場合、i
-
parent [edges [i、0]]:=-1、parent [edges [i、1]]:=-1
-
ランク[エッジ[i、0]]:=-1、ランク[エッジ[i、1]]:=1
-
-
配列を定義します
-
初期化i:=0の場合、i
-
u:=エッジ[i、0]
-
v:=エッジ[i、1]
-
unionn(u、v)がゼロの場合、-
-
ans:=edge [i]
-
-
-
ansを返す
例
理解を深めるために、次の実装を見てみましょう-
#include <bits/stdc++.h> using namespace std; void print_vector(vector v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } const int N = 1000; class Solution { public: int parent[N + 5]; int rank[N + 5]; int getParent(int n){ if (parent[n] == -1) return n; return parent[n] = getParent(parent[n]); } bool unionn(int a, int b){ int pa = getParent(a); int pb = getParent(b); if (pa == pb) return false; if (rank[pa] > rank[pb]) { rank[pa] += rank[pb]; parent[pb] = pa; } else { rank[pb] += rank[pa]; parent[pa] = pb; } return true; } vector<int> findRedundantConnection(vector<vector<int>>& edges) { int n = edges.size(); for (int i = 0; i < n; i++) { parent[edges[i][0]] = parent[edges[i][1]] = -1; rank[edges[i][0]] = rank[edges[i][1]] = 1; } vector<int> ans; for (int i = 0; i < n; i++) { int u = edges[i][0]; int v = edges[i][1]; if (!unionn(u, v)) { ans = edges[i]; } } return ans; } }; main(){ Solution ob; vector<vector<int>> v = {{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}; print_vector(ob.findRedundantConnection(v)); }
入力
{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}
出力
[1, 4, ]
-
C++でのリスのシミュレーション
木、リス、そしていくつかのナッツがあります。位置は、2Dグリッドのセルで表されます。あなたの目標は、リスがすべてのナッツを集めて、それらを1つずつ木の下に置くための最小距離を見つけることです。リスは一度に最大で1つのナットしかとることができず、隣接するセルに向かって上下左右の4つの方向に移動できます。距離は移動回数で表されます。 したがって、入力が高さ:5幅:7木の位置:[2,2]リス:[4,4]ナッツ:[[3,0]、[2,5]]の場合、出力は12になります。 、 これを解決するには、次の手順に従います- 関数calc()を定義します。これには、x1、y1、x2、y2、が必要で
-
C++の長方形エリアII
(軸に沿った)長方形のリストがあるとします。ここで、各rectangle [i] ={x1、y1、x2、y2}です。ここで、(x1、y1)は左下隅のポイントであり、(x2、y2)は右上隅のポイントです。 i番目の長方形。 平面内のすべての長方形でカバーされる総面積を見つける必要があります。答えは非常に大きい可能性があるため、モジュロ10 ^ 9+7を使用できます。 したがって、入力が次のような場合 その場合、出力は6になります。 これを解決するには、次の手順に従います- m =10 ^ 9 + 7 関数add()を定義します。これには、a、b、が必要です。 r