题目链接：https://vjudge.net/problem/UVA-11324

题解：

题意：给出一张有向图，求一个结点数最大的结点集，使得任意两个结点u、v，要么u能到达v， 要么v能到达u（u和v也可以互相到达）。

1.可知在一个强连通分量中，任意两个点都可以互相到达。那么我们就对每个强连通分量进行缩点，并记录每个分量的结点个数。

2.缩点之后，就是一张有向无环图了，这时就转化为求：从有向无环图中找出一条权值之和最大的路径。简单的记忆化搜索即可实现。

前向星建图 + 前向星重建：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const LL LNF = 2e18;

 const int MAXM = 5e4+;

 const int MAXN = 1e3+;

 struct Edge

 {

     int to, next;

 }edge[MAXM], edge0[MAXM];   //edge为初始图， edge0为重建图

 int tot, head[MAXN], tot0, head0[MAXN];

 int Index, dfn[MAXN], low[MAXN];

 int top, Stack[MAXN], instack[MAXN];

 int scc, belong[MAXN], num[MAXN];

 int dp[MAXN];

 void addedge(int u, int v, Edge edge[], int head[], int &tot)

 {

     edge[tot].to = v;

     edge[tot].next = head[u];

     head[u] = tot++;

 }

 void Tarjan(int u)

 {

     dfn[u] = low[u] = ++Index;

     Stack[top++] = u;

     instack[u] = true;

     for(int i = head[u]; i!=-; i = edge[i].next)

     {

         int v = edge[i].to;

         if(!dfn[v])

         {

             Tarjan(v);

             low[u] = min(low[u], low[v]);

         }

         else if(instack[v])

             low[u] = min(low[u], dfn[v]);

     }

     if(dfn[u]==low[u])

     {

         int v;

         scc++;

         do

         {

             v = Stack[--top];

             instack[v] = false;

             belong[v] = scc;

             num[scc]++;

         }while(v!=u);

     }

 }

 int dfs(int u)

 {

     if(dp[u]!=-) return dp[u];

     dp[u] = num[u];

     for(int i = head0[u]; i!=-; i = edge0[i].next)

     {

         int v = edge0[i].to;

         dp[u] = max(dp[u], num[u]+dfs(v));

     }

     return dp[u];

 }

 void init()

 {

     tot = tot0 = ;

     memset(head, -, sizeof(head));

     memset(head0, -, sizeof(head0));

     Index = top = ;

     memset(dfn, , sizeof(dfn));

     memset(low, , sizeof(low));

     memset(instack, , sizeof(instack));

     scc = ;

     memset(num, , sizeof(num));

     memset(dp, -, sizeof(dp));

 }

 int main()

 {

     int n, m, T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d", &n, &m);

         init();

         for(int i = ; i<=m; i++)

         {

             int u, v;

             scanf("%d%d", &u, &v);

             addedge(u, v, edge, head, tot);

         }

         for(int i = ; i<=n; i++)

             if(!dfn[i])

                 Tarjan(i);

         for(int u = ; u<=n; u++)   //重建建图

         for(int i = head[u]; i!=-; i = edge[i].next)

         {

             int tmpu = belong[u];

             int tmpv = belong[edge[i].to];

             if(tmpu!=tmpv)

                 addedge(tmpu, tmpv, edge0, head0, tot0);

         }

         int ans = ;

         for(int i = ; i<=scc; i++)

             if(dp[i]==-)

                 ans = max(ans, dfs(i));

         printf("%d\n", ans);

     }

 }

前向星建图 + vector重建：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const int MAXM = 5e4+;

 const int MAXN = 1e3+;

 struct Edge

 {

     int to, next;

 }edge[MAXM];

 int tot, head[MAXN];

 vector<int>g[MAXN];

 int Index, dfn[MAXN], low[MAXN];

 int top, Stack[MAXN], instack[MAXN];

 int scc, belong[MAXN], num[MAXN];

 int dp[MAXN];

 void addedge(int u, int v)

 {

     edge[tot].to = v;

     edge[tot].next = head[u];

     head[u] = tot++;

 }

 void Tarjan(int u)

 {

     dfn[u] = low[u] = ++Index;

     Stack[top++] = u;

     instack[u] = true;

     for(int i = head[u]; i!=-; i = edge[i].next)

     {

         int v = edge[i].to;

         if(!dfn[v])

         {

             Tarjan(v);

             low[u] = min(low[u], low[v]);

         }

         else if(instack[v])

             low[u] = min(low[u], dfn[v]);

     }

     if(dfn[u]==low[u])

     {

         int v;

         scc++;

         do

         {

             v = Stack[--top];

             instack[v] = false;

             belong[v] = scc;

             num[scc]++;

         }while(v!=u);

     }

 }

 int dfs(int u)

 {

     if(dp[u]!=-) return dp[u];

     dp[u] = num[u];

     for(int i = ; i<g[u].size(); i++)

     {

         int v = g[u][i];

         dp[u] = max(dp[u], num[u]+dfs(v));

     }

     return dp[u];

 }

 void init(int n)

 {

     tot = ;

     memset(head, -, sizeof(head));

     Index = top = ;

     memset(dfn, , sizeof(dfn));

     memset(low, , sizeof(low));

     memset(instack, , sizeof(instack));

     scc = ;

     memset(num, , sizeof(num));

     memset(dp, -, sizeof(dp));

     for(int i = ; i<=n; i++)

         g[i].clear();

 }

 int main()

 {

     int n, m, T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d", &n, &m);

         init(n);

         for(int i = ; i<=m; i++)

         {

             int u, v;

             scanf("%d%d", &u, &v);

             addedge(u, v);

         }

         for(int i = ; i<=n; i++)

             if(!dfn[i])

                 Tarjan(i);

         for(int u = ; u<=n; u++)

         for(int i = head[u]; i!=-; i = edge[i].next)

         {

             int tmpu = belong[u];

             int tmpv = belong[edge[i].to];

             if(tmpu!=tmpv)

                 g[tmpu].push_back(tmpv);

         }

         int ans = ;

         for(int i = ; i<=scc; i++)

             if(dp[i]==-)

                 ans = max(ans, dfs(i));

         printf("%d\n", ans);

     }

 }

vector建图 + vector重建：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const int MAXN = 1e3+;

 vector<int>G[MAXN], g[MAXN];

 int Index, dfn[MAXN], low[MAXN];

 int top, Stack[MAXN], instack[MAXN];

 int scc, belong[MAXN], num[MAXN];

 int dp[MAXN];

 void Tarjan(int u)

 {

     dfn[u] = low[u] = ++Index;

     Stack[top++] = u;

     instack[u] = true;

     for(int i = ; i<G[u].size(); i++)

     {

         int v = G[u][i];

         if(!dfn[v])

         {

             Tarjan(v);

             low[u] = min(low[u], low[v]);

         }

         else if(instack[v])

             low[u] = min(low[u], dfn[v]);

     }

     if(dfn[u]==low[u])

     {

         int v;

         scc++;

         do

         {

             v = Stack[--top];

             instack[v] = false;

             belong[v] = scc;

             num[scc]++;

         }while(v!=u);

     }

 }

 int dfs(int u)

 {

     if(dp[u]!=-) return dp[u];

     dp[u] = num[u];

     for(int i = ; i<g[u].size(); i++)

     {

         int v = g[u][i];

         dp[u] = max(dp[u], num[u]+dfs(v));

     }

     return dp[u];

 }

 void init(int n)

 {

     Index = top = ;

     memset(dfn, , sizeof(dfn));

     memset(low, , sizeof(low));

     memset(instack, , sizeof(instack));

     scc = ;

     memset(num, , sizeof(num));

     memset(dp, -, sizeof(dp));

     for(int i = ; i<=n; i++)

     {

         G[i].clear();

         g[i].clear();

     }

 }

 int main()

 {

     int n, m, T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d", &n, &m);

         init(n);

         for(int i = ; i<=m; i++)

         {

             int u, v;

             scanf("%d%d", &u, &v);

             G[u].push_back(v);

         }

         for(int i = ; i<=n; i++)

             if(!dfn[i])

                 Tarjan(i);

         for(int u = ; u<=n; u++)

         for(int i = ; i<G[u].size(); i++)

         {

             int tmpu = belong[u];

             int tmpv = belong[G[u][i]];

             if(tmpu!=tmpv)

                 g[tmpu].push_back(tmpv);

         }

         int ans = ;

         for(int i = ; i<=scc; i++)

             if(dp[i]==-)

                 ans = max(ans, dfs(i));

         printf("%d\n", ans);

     }

 }

最新文章

  1. sql 查询当前数据库所有表格以及所有表格数据条数
  2. CSS魔法堂：Absolute Positioning就这个样
  3. Javascript包含对象的数组去重
  4. cogs896 圈奶牛
  5. go mobile 得生命周期事件
  6. find中的 time 参数
  7. Python3 - 时间处理与定时任务
  8. iOS中ASI和AFN的区别
  9. Cordova自定义插件
  10. smarty模版使用php标签，获取模版变量!
  11. WPF事件,路由事件
  12. Unity在安卓的一些路径
  13. 如何掌握并提高linux运维技能
  14. Android 音视频开发(七)： 音视频录制流程总结
  15. xgboost 最优参数, df某一个字段进行字符串搜索
  16. java学习之成员内部类
  17. 使用find命令查找文件
  18. February 19th, 2018 Week 8th Monday
  19. @RequestBody
  20. reids遇到问题

热门文章

  1. intellij idea2016
  2. Linux如何查看CPU负载
  3. CodeForces 21 A+B
  4. 动手实操：如何用 Python 实现人脸识别，证明这个杨幂是那个杨幂？
  5. Go 在游戏行业中的工程实践
  6. Java并发编程：自己动手写一把可重入锁
  7. hdu 1565 状态压缩dp
  8. lightoj 1293 - Document Analyzer [ 两指针 + 字符串 ]
  9. Spring Cloud（9）：Config配置中心
  10. spring-security 理解 笔记 介绍以及使用（持续更新）