UVA11324 The Largest Clique —— 强连通分量 + 缩点 + DP

时间：2023-03-09 15:51:58
UVA11324 The Largest Clique —— 强连通分量 + 缩点 + DP

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

UVA11324 The Largest Clique —— 强连通分量 + 缩点 + DP

UVA11324 The Largest Clique —— 强连通分量 + 缩点 + DP

题解：

题意：给出一张有向图，求一个结点数最大的结点集，使得任意两个结点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);

     }

 }

相关文章