방향 그래프 G의 인접 행렬이 있다고 가정합니다. 그래프가 비어 있을 때까지 다음 작업을 반복합니다. G에서 하나의 정점을 선택한 다음 해당 정점과 일부 가장자리를 따라 해당 정점에서 도달할 수 있는 모든 정점을 지웁니다. 꼭짓점을 지우면 해당 꼭짓점에 발생한 가장자리도 지워집니다. 작업이 완료되는 예상 횟수를 찾아야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은 1.6667이 됩니다. 처음에는 정점 A를 선택하고 모든 정점을 제거하고 정점 B를 선택하면 B와 C를 제거하고 두 번째 작업에서 A를 선택하여 제거하기 때문에 출력은 1.6667이 됩니다. 마찬가지로 C를 선택하면 2개의 작업이 필요합니다. 따라서 평균은 (1+2+2)/3 =1.6667입니다.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
n := size of G for initialize i := 0, when i < n, update (increase i by 1), do: G[i, i] := 1 for initialize k := 0, when k < n, update (increase k by 1), do: for initialize i := 0, when i < n, update (increase i by 1), do: for initialize j := 0, when j < n, update (increase j by 1), do: if G[i, k] is non-zero and G[k, j] is non-zero, then: G[i, j] := 1 ans := 0 for initialize i := 0, when i < n, update (increase i by 1), do: k := 0 for initialize j := 0, when j < n, update (increase j by 1), do: if G[j, i] is non-zero, then: (increase k by 1) ans := ans + 1.0 / k return ans
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
double solve(vector<vector<int>> G){
int n = G.size();
for (int i = 0; i < n; ++i)
G[i][i] = 1;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (G[i][k] && G[k][j])
G[i][j] = 1;
double ans = 0;
for (int i = 0; i < n; ++i){
int k = 0;
for (int j = 0; j < n; ++j)
if (G[j][i])
++k;
ans += 1.0 / k;
}
return ans;
}
int main(){
vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
cout << solve(G) << endl;
} 입력
{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } } 출력
1.66667