首页 > 代码库 > UVAoj 11324 - The Largest Clique(tarjan + dp)
UVAoj 11324 - The Largest Clique(tarjan + dp)
题意：给定一个有向图，寻找一个点数最大集合，使得这个集合中的任意两个点
u,v, 都有u->v 或者 v->u 或者u<==>v
思路：首先将强连通分量通过tarjan算法求出来，然后进行缩点，也就是每一个缩点
所组成的图就是一个DAG图！令每一个点的权值就是这个缩点所包含节点（也就是对应的
强连通分量的节点数目），因为强连通分量的任意的两个节点都是相互可达的，那么这个
缩点要么选要么不选，问题就转换成了DAG图上的最长路径！
1 #include<iostream> 2 #include<queue> 3 #include<stack> 4 #include<cstring> 5 #include<cstdio> 6 #include<algorithm> 7 #include<vector> 8 #define N 1005 9 using namespace std; 10 11 struct EDGE{ 12 int u, v, nt; 13 EDGE(){} 14 EDGE(int u, int v, int nt) : u(u), v(v), nt(nt){} 15 }; 16 17 int first[N]; 18 vector<EDGE>g; 19 vector<EDGE>gg; 20 int scc_cnt, dfs_clock; 21 int scc[N]; 22 int pre[N], low[N]; 23 int dp[N], cnt[N]; 24 25 int in[N]; 26 int n, m; 27 stack<int>s; 28 29 void dfs(int u){ 30 pre[u] = low[u] = ++dfs_clock; 31 s.push(u); 32 for(int i = first[u]; ~i; i = g[i].nt){ 33 int v = g[i].v; 34 if(!pre[v]){ 35 dfs(v); 36 low[u] = min(low[u], low[v]); 37 }else if(!scc[v]) 38 low[u] = min(low[u], pre[v]); 39 } 40 if(low[u] == pre[u]){ 41 ++scc_cnt; 42 while(1){ 43 ++cnt[scc_cnt]; 44 int x = s.top(); s.pop(); 45 scc[x] = scc_cnt; 46 if(x==u) break; 47 } 48 } 49 } 50 51 void addEdge(int u, int v){ 52 g.push_back(EDGE(u, v, first[u])); 53 first[u] = g.size() - 1; 54 } 55 56 void tarjans(){ 57 memset(pre, 0, sizeof(pre)); 58 memset(scc, 0, sizeof(scc)); 59 memset(cnt, 0, sizeof(cnt)); 60 memset(dp, 0, sizeof(dp)); 61 memset(in, 0, sizeof(in)); 62 scc_cnt = 0; 63 dfs_clock = 0; 64 for(int i=1; i<=n; ++i) 65 if(!pre[i]) dfs(i); 66 int len = g.size(); 67 memset(first, -1, sizeof(first)); 68 gg.clear(); 69 for(int i=0; i<len; ++i) 70 if(scc[g[i].u] != scc[g[i].v]){ 71 in[scc[g[i].v]]++; 72 gg.push_back(EDGE(scc[g[i].u], scc[g[i].v], first[scc[g[i].u]])); 73 first[scc[g[i].u]] = gg.size() - 1; 74 } 75 int maxN = 0; 76 queue<int>q; 77 for(int i=1; i<=scc_cnt; ++i) 78 if(!in[i]){ 79 dp[i] = cnt[i]; 80 q.push(i); 81 if(maxN < dp[i]) maxN = dp[i]; 82 } 83 while(!q.empty()){ 84 int u = q.front(); q.pop(); 85 for(int i=first[u]; ~i; i = gg[i].nt){ 86 int v = gg[i].v; 87 dp[v] = max(dp[v], dp[u] + cnt[v]); 88 q.push(v); 89 if(maxN < dp[v]) maxN = dp[v]; 90 } 91 } 92 printf("%d\n", maxN); 93 } 94 95 int main(){ 96 int t; 97 scanf("%d", &t); 98 while(t--){ 99 memset(first, -1, sizeof(first));100 scanf("%d%d", &n, &m);101 while(m--){102 int u, v;103 scanf("%d%d", &u, &v);104 addEdge(u, v);105 }106 tarjans(); 107 g.clear();108 }109 return 0;110 }
UVAoj 11324 - The Largest Clique(tarjan + dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。