首页 > 代码库 > UVA11324 The Largest Clique,有向图,最大团的结点数
UVA11324 The Largest Clique,有向图,最大团的结点数
点击打开链接
有向图
把强联通分量缩点后得到一个DAG,然后DP。
</pre><pre name="code" class="cpp">#include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <vector> #include <queue> using namespace std; const int maxn = 1000 + 10; vector<int> G[maxn]; int dfn[maxn], low[maxn], sccno[maxn], dfs_clock, scc_cnt; stack<int> S; void dfs(int u) { dfn[u] = low[u] = ++dfs_clock; S.push(u); for(int i=0; i<G[u].size(); ++i) { int v = G[u][i]; if(!dfn[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if(!sccno[v]) { low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x==u) break; } } } void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof sccno ); memset(dfn, 0, sizeof dfn ); for(int i=0; i<n; ++i) { if(!dfn[i]) dfs(i); } } int size[maxn], TG[maxn][maxn];//缩点后的SCC图-邻接矩阵 int d[maxn]; int dp(int u) { int & ans = d[u]; if(ans>=0) return ans; ans = size[u]; for(int v=1; v<=scc_cnt; ++v) if(u != v && TG[u][v]) ans=max(ans, dp(v)+size[u]); return ans; } int main() { int T, n, m; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i=0; i<n; ++i) G[i].clear(); for(int i=0; i<m; ++i) { int u, v; scanf("%d%d", &u, &v); u--; v--; G[u].push_back(v); } find_scc(n); memset(TG, 0, sizeof TG ); memset(size, 0, sizeof size ); for(int i=0; i<n; ++i) { size[sccno[i]]++; for(int j=0; j<G[i].size(); ++j) TG[sccno[i]][sccno[G[i][j]]] = 1;// 构造SCC图 } int ans = 0; memset(d, -1, sizeof d ); for(int i=1; i<=scc_cnt; ++i) { ans = max(ans, dp(i)); } printf("%d\n", ans); } return 0; }
UVA11324 The Largest Clique,有向图,最大团的结点数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。