洛谷 P2272 【最大半连通子图】

• 题库：洛谷
• 题号：2272
• 题目：最大半连通子图
• link：https://www.luogu.org/problem/P2272

• 给52分的前排提醒：记得在Tarjan后去重边，否则方案数会最长链的数量会受到影响

• 题意简化（这题的题面太毒瘤了）：给定一个图，求这个图的最长链所包含的节点个数以及最长链的个数

• 思路：我们先用Tarjan把图进行缩点（及把能够互相到达的一个子图缩成一个点，并记录当前强连通分量的节点数，这样不会对结果进行影响，当搜到这个强连通分量时，我们只需要把当前强连通分量的节点数加上就好了），然后我们对这个缩过点的图重新进行建边（注意：重新建完图后，可能会有重边，需要判重，否则最后最长链的数量会受到影响），最后我们拓扑加dp把最长链的节点的数量和最长链的数量求出，定义dis[i]表示从第i个点开始到达任意点的最长链的节点的个数，cnt[i]表示从i开始可以到达的最长链的数量，并且记录最长链的节点个数。最后枚举1 ~ n，如果dis[i] == 最长链的节点的个数，那么ans就加上当前点可以到达的最长链的数量，并且%MOD，最后先输出最长链的节点的个数，再输出ans。（如何拓扑 + dp在代码中讲）

• code：

    1 #include <bits/stdc++.h>
    2 #define INF 0x3f3f3f3f
    3 using namespace std;
    4 map < int, map < int, int > > mp;//map判重 
    5 stack < int > pru;
    6 int n, m, MOD, head[100001], vis[100001], dis[100001], col[100001], color, dfn[100001], low[100001], num, in[100001], out[100001], z, sum[100001], cnt[100001], ans, maxn;//in是入度，out是出度，sum是当前强连通分量中节点的个数 
    7 struct node
    8 {
    9     int next, to;
   10 }stu[1000001];
   11 queue < node > G;//临时存边 
   12 inline void add(int x, int y)
   13 {
   14     stu[++num].next = head[x];
   15     stu[num].to = y;
   16     head[x] = num;
   17     return;
   18 }
   19 inline void tarjan(int u)//标准Tarjan板子 
   20 {
   21     dfn[u] = low[u] = ++z;
   22     vis[u] = 1;
   23     pru.push(u);
   24     for(register int i = head[u]; i; i = stu[i].next)
   25     {
   26         int k = stu[i].to;
   27         if(!vis[k])
   28         {
   29             tarjan(k);
   30             low[u] = min(low[u], low[k]);
   31         }
   32         else if(!col[k])
   33         {
   34             low[u] = min(low[u], dfn[k]);
   35         }
   36     }
   37     if(dfn[u] == low[u])
   38     {
   39         col[u] = ++color;
   40         ++sum[color];//节点数++ 
   41         while(pru.top() != u)
   42         {
   43             col[pru.top()] = color;
   44             ++sum[color];//节点数++ 
   45             pru.pop();
   46         }
   47         pru.pop();
   48     }
   49     return;
   50 }
   51 inline void init()//清空边 
   52 {
   53     memset(head, 0, sizeof(head));
   54     for(register int i = 1; i <= num; ++i)
   55     {
   56         stu[i].next = 0;
   57         stu[i].to = 0;
   58     }
   59     num = 0;
   60     return;
   61 }
   62 inline void add_edge()//重新建边 
   63 {
   64     for(register int u = 1; u <= n; ++u)
   65     {
   66         for(register int i = head[u]; i; i = stu[i].next)
   67         {
   68             int k = stu[i].to;
   69             if(col[k] != col[u])
   70             {
   71                 if(!mp[col[u]][col[k]])//判重 
   72                 {    
   73                     G.push(node{col[u], col[k]});
   74                     mp[col[u]][col[k]] = 1;
   75                 }
   76             }
   77         }
   78     }
   79     init();
   80     while(!G.empty())
   81     {
   82         add(G.front().next, G.front().to);
   83         ++in[G.front().to];//入度++ 
   84         ++out[G.front().next];//出度++ 
   85         G.pop();
   86     }
   87     return;
   88 }
   89 inline void dfs(int u)
   90 {
   91     vis[u] = 1;//标记当前点已访问过 
   92     if(!out[u])//没有出度代表已经到头了 
   93     {
   94         dis[u] = sum[u];//既然是最后一个点，那么最长链就是这个点的节点数 
   95         cnt[u] = 1;//最长链数量为1 
   96         maxn = max(maxn, dis[u]);//取max 
   97         return;
   98     }
   99     for(register int i = head[u]; i; i = stu[i].next)//枚举出边 
  100     {
  101         int k = stu[i].to;
  102         if(!vis[k])//没有访问过，继续访问 
  103         {
  104             dfs(k);
  105         }
  106         if(dis[k] + sum[u] > dis[u])//dp方程，及如果当前最长链长度，比自己的出边的最长链长度 + 自己的节点数小的话 
  107         {
  108             dis[u] = dis[k] + sum[u];//转换 
  109             cnt[u] = cnt[k];//变换 
  110         }
  111         else if(dis[k] + sum[u] == dis[u])//如果相等
  112         {
  113             cnt[u] = (cnt[u] + cnt[k]) % MOD;//加上自己出边的最长链的数量，别忘了取模数 
  114         }
  115         maxn = max(maxn, dis[u]);//取max 
  116     }
  117     return;
  118 }
  119 signed main()
  120 {
  121     scanf("%d %d %d", &n, &m, &MOD);
  122     for(register int i = 1, x, y; i <= m; ++i)
  123     {
  124         scanf("%d %d", &x, &y);
  125         add(x, y);//加边 
  126     }
  127     for(register int i = 1; i <= n; ++i)
  128     {
  129         if(!vis[i])
  130         {
  131             tarjan(i);//tarjan 
  132         }
  133     }
  134     add_edge();//重建边 
  135     memset(vis, 0, sizeof(vis));//清空 
  136     for(register int i = 1; i <= color; ++i)//记住，现在n个点化为color个强连通分量 
  137     {
  138         if(!in[i])//从没有入度的点开始搜 
  139         {
  140             dfs(i);
  141         }
  142     }
  143     for(register int i = 1; i <= color; ++i) 
  144     {
  145         if(dis[i] == maxn)//如果从当前点开始的最长链和maxn相等(他就是最长链之一) 
  146         {
  147             ans = (ans + cnt[i]) % MOD;//ans加上他的最长链的数量，别忘了取MOD 
  148         }
  149     }
  150     printf("%d\n%d", maxn, ans);//记得换行 + 输出顺序 
  151     return 0;
  152 }

   

洛谷 P2272 【最大半连通子图】

原文：https://www.cnblogs.com/qqq1112/p/11625728.html