|
最大团问题
DP + DFS
最大团问题
DP + DFS
| INIT: g[][]
邻接矩阵
;
邻接矩阵
;
| CALL: res = clique(n);
*==================================================*/
int
g[V][V], dp[V], stk[V][V], mx;
g[V][V], dp[V], stk[V][V], mx;
if
(0 == ns) {
(0 == ns) {
if
(dep > mx) mx = dep;
(dep > mx) mx = dep;
return
1;
1;
}
int
i, j, k, p, cnt;
i, j, k, p, cnt;
for
(i = 0; i
(i = 0; i
k = stk[dep][i]; cnt = 0;
if
(dep + dp[k]
return
0;
(dep + dp[k]
return
0;
for
(j = i + 1; j
(j = i + 1; j
p = stk[dep][j];
if
(g[k][p]) stk[dep + 1][cnt++] = p;
(g[k][p]) stk[dep + 1][cnt++] = p;
}
dfs(n, cnt, dep + 1);
}
return
1;
1;
}
int
clique(
int
n){
clique(
int
n){
int
i, j, ns;
i, j, ns;
for
(mx = 0, i = n – 1; i >= 0; i–) {
(mx = 0, i = n – 1; i >= 0; i–) {
// vertex: 0 ~ n-1
for
(ns = 0, j = i + 1; j
(ns = 0, j = i + 1; j
if
(g[i][j]) stk[1][ ns++ ] = j;
(g[i][j]) stk[1][ ns++ ] = j;
dfs(n, ns, 1); dp[i] = mx;
}
return
mx;
mx;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 把VS Code打造成后端开发的宇宙IDE，也挺爽
本文首发自「慕课网」，想了解更多IT干货内容，程序员圈内热闻，欢迎关注！ 作者：维生素P|慕课网优质作者 工欲善其事必先利其器，提高程序员的开发效率必须要有一个好的开发工具。而一旦提到开发工具，那么就绝对会提到火爆到被称为宇宙IDE的VS Code。 VS C…
