iの最大値を見つけるためのC++プログラム
整数「seq」の順列と、0からn-1までの整数を含むサイズmの整数ペア「ペア」の配列があるとします。ここで、seqに対して次の操作を可能な限り何度も実行してseq[ i] =i(0≤i
-
0 <=j
を入れ替える必要があります。
操作を複数回実行した後、seq [i]=iとなるようにiの最大値を見つける必要があります。
したがって、入力がn =4、m =2、seq ={0、3、2、1}、ペア={{0、1}、{2、3}}の場合、出力は2になります。
可能な最大値は2です。
これを解決するには、次の手順に従います-
N := 100 Define an array tp of size: N. Define arrays vtmp, vis of size N. Define a function dfs(), this will take j, k, tp[j] := k insert j at the end of vtmp[k] for each value b in vis[j], do: if tp[b] is not equal to 0, then: Ignore following part, skip to the next iteration dfs(b, k) res := 0 for initialize i := 0, when i < n, update (increase i by 1), do: if seq[i] is same as i, then: (increase res by 1) for initialize i := 0, when i < m, update (increase i by 1), do: a := first value of pairs[i] b := second value of pairs[i] insert b at the end of vis[a] insert a at the end of vis[b] idx := 1 for initialize i := 0, when i < n, update (increase i by 1), do: if tp[i] is same as 0, then: dfs(i, idx) for each element j in vtmp[idx], do: if tp[seq[j]] is same as idx and seq[j] is not equal to j, then: (increase res by 1) (increase idx by 1) print(res)
例
理解を深めるために、次の実装を見てみましょう-
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; #define N 100 int tp[N]; vector<int> vtmp[N], vis[N]; void dfs(int j, int k){ tp[j] = k; vtmp[k].push_back(j); for(auto b : vis[j]) { if(tp[b] != 0) continue; dfs(b, k); } } void solve(int n, int m, int seq[], vector<pair<int, int>> pairs) { int res = 0; for(int i = 0; i < n; i++){ if(seq[i] == i) res++; } for(int i = 0; i < m; i++){ int a = pairs[i].first; int b = pairs[i].second; vis[a].push_back(b); vis[b].push_back(a); } int idx = 1; for(int i = 0; i < n; i++) { if(tp[i] == 0) { dfs(i, idx); for(auto j: vtmp[idx]){ if(tp[seq[j]] == idx && seq[j] != j) res++; } idx++; } } cout<< res; } int main() { int n = 4, m = 2, seq[] = {0, 3, 2, 1}; vector<pair<int,int>> pairs = {{0, 1}, {2, 3}}; solve(n, m, seq, pairs); return 0; }
入力
4, 2, {0, 3, 2, 1}, {{0, 1}, {2, 3}}
出力
2
-
与えられたグラフのブリッジエッジの数を見つけるためのC++プログラム
n個の頂点とm個のエッジを含む重み付けされていない無向グラフが与えられたとします。グラフのブリッジエッジは、グラフを削除するとグラフが切断されるエッジです。与えられたグラフでそのようなグラフの数を見つける必要があります。グラフには、平行なエッジや自己ループは含まれていません。 したがって、入力がn =5、m =6、edges ={{1、2}、{1、3}、{2、3}、{2、4}、{2、5}、{3 、5}}の場合、出力は1になります。 グラフには、{2、4}のブリッジエッジが1つだけ含まれています。 これを解決するには、次の手順に従います- mSize := 100 Define an
-
グラフから減らすことができるスコアの最大量を見つけるためのC++プログラム
n個の頂点とm個のエッジを持つ重み付きの無向グラフがあるとします。グラフのスコアは、グラフ内のすべてのエッジの重みの加算として定義されます。エッジの重みは負の値になる可能性があり、それらを削除するとグラフのスコアが増加します。グラフを接続したまま、グラフからエッジを削除して、グラフのスコアを最小にする必要があります。減らすことができるスコアの最大量を見つける必要があります。 グラフは配列edgesで与えられ、各要素は{weight、{vertex1、vertex2}}の形式です。 したがって、入力がn =5、m =6、edges ={{2、{1、2}}、{2、{1、3}}、{1、{2、3}