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 }

View Code

轉載于:https://www.cnblogs.com/hujunzheng/p/4019695.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531604.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531604.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531604.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！