사회망 서비스
사회망 서비스
얼리 어댑터인지 아닌지 2개의 상태가 주어진다
-
root i 가 얼리어답터일 경우: i의 child node는 얼리어답터일 수도 있고 아닐 수도 있다
-
root i가 얼리어답터가 아닐 경우: i의 child node는 무조건 얼리어답터이어야 한다
d[i][state]: state 0일 때 정점이 얼리어답터가 아닌경우, otherwise 1
d[i][0] = 0 d[i][0] += d[child][1]
d[i][1] = 1 d[i][1] += min(d[child][0], d[child][1])
최상위 root node가 1일 경우 해는 min(d[1][0], d[1][1]) 이다
leaf에서부터 시작한다
private static void sns(int curr) {
d[curr][1]++;
visited[curr] = true;
for (int next: adj.get(curr)) {
if (visited[next] == false) {
sns(next);
d[curr][0] += d[next][1];
d[curr][1] += Math.min(d[next][0], d[next][1]);
}
}
}
이런 구현도 가능하다
private static int sns(int curr, int adt) {
if (d[curr][adt] != -1) {
return d[curr][adt];
}
visited[curr] = true;
if (adt == 1) {
d[curr][adt] = 1;
for (int next: adj.get(curr)) {
if (visited[next] == false) {
d[curr][adt] += Math.min(sns(next, 0), sns(next, 1));
}
}
} else {
d[curr][adt] = 0;
for (int next: adj.get(curr)) {
if (visited[next] == false) {
d[curr][adt] += sns(next, 1);
}
}
}
visited[curr] = false;
return d[curr][adt];
}