寒假学习笔记【匠心制作，图文并茂】——1.20拓扑、强连通分量、缩点

文章目录

• 前言
• 拓扑排序
• • 拓扑排序是怎么运作的
  • 拓扑排序的好处
  • 强连通分量
  • • 强连通是什么
    • 强连通分量是什么
    • 如何求 SCC
    • 缩点

      前言

      更新的稍微有点晚……

      因为强连通分量这一块难学且知识点多，学习时间久了亿点，所以直到现在才更新。

      拓扑排序

      OI-Wiki 是这么定义拓扑排序的：

      拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序。

      这个感觉不是很像定义，更像是它在干什么，我们来重新定义一下拓扑排序：

      拓扑排序是一种将一个有向无环图（Directed Acyclic Graph，简称 DAG）按照一定顺序对所有节点进行排序的算法。

      注意：只能在有向无环图上跑拓扑。

      拓扑排序是怎么运作的

      接下来我就要开始操作了，注意步骤：

      1. 取出图中入度为 0 0 0 的点，加入队列。
      2. 取出队头，将与队头相连的点的入度全减 1 1 1。
      3. 将图上入度为 0 0 0 的点加入队列。
      4. 重复执行 2 2 2、 3 3 3 操作。
      5. 想你的诗和远方吧……

      没看明白的观众就请看下面的模拟，看明白了的，也还是看一下案例吧。

      我们先随机生成一个 DAG：

      

      首先按照第一步：取出图中入度为 0 0 0 的点并放入队列（如果你连入度是啥都不知道，那你就不应该出现在这）。图中入度为 0 0 0 的点不就是 1 1 1 吗？此时队列中有一个 1 1 1。

      

      然后进行第二步：取出队头，将与队头相连的点的入度全减 1 1 1。队头就是 1 1 1，那么我们取出 1 1 1 并将所有与队头相连的点入度减 1 1 1，整张图就相当于变成了这样：

      

      队列此时为空。

      然后进行第三步：将图上入度为 0 0 0 的点加入队列。图上入度为 0 0 0 的点有 2 2 2 和 3 3 3，所以把它们加入队列，于是队列变成了这样：

      

      然后就是重复执行以上操作……

      最后，我们得到的拓扑序就是这三种中的一种：1 2 3 6 4 5、1 3 2 4 6 5、1 3 2 6 4 5。

      不难看出，一张图的拓扑序可以有很多个。所以这类题一般都是 SPJ（Special Judge）。

      以 洛谷 B3644 为例，代码如下：

      #include
      #define int long long
      using namespace std;
      int n,rd[106];
      vectorv[106];
      queueq;
      signed main()
      {
      	cin>>n;
      	for(int x,i=1;i
      		while(cin>x&&x)
      		{
      			v[i].emplace_back(x);
      			rd[x]++;
      		}
      	}
      	for(int i=1;i
      		if(rd[i]==0)
      		{
      			q.emplace(i);
      		}
      	}
      	while(!q.empty())//第二、三步
      	{
      		int x=q.front();
      		q.pop();
      		cout
      			rd[i]--;
      			if(rd[i]==0)
      			{
      				q.emplace(i);
      			}
      		}
      	}
      	return 0;
      }
      
          dfn[x]=low[x]=++ti;//记录编号
          st.emplace(x);
          ins[x]=1;
          for(auto i:v[x])
          {
              if(!dfn[i])
              {
                  tarjan(i);
                  low[x]=min(low[x],low[i]);//更新
              }
              else if(ins[i])
              {
                  low[x]=min(low[x],dfn[i]);
              }
          }
          if(low[x]==dfn[x])//找到 SCC
          {
              cnt++;
              while(1)
              {
                  int u=st.top();
                  st.pop();
                  ins[u]=0;
                  belong[u]=cnt;//记录下来每个点属于哪个 SCC（主要是为了缩点）
                  b[u]=cnt;
                  vv[cnt].emplace_back(u);//记录下来有哪些点
                  if(u==x)
                  {
                      break;
                  }
              }
          }
      }
      signed main()
      {
          cinnm;
          for(int x,y,i=1;i
              cinx>>y;
              v[x].emplace_back(y);
          }
          for(int i=1;i
              if(!dfn[i])
              {
                  tarjan(i);
              }
          }
          for(int i=1;i
              sort(vv[i].begin(),vv[i].end());
          }
          cout
              if(!vis[b[i]])
              {
                  for(auto j:vv[b[i]])
                  {
                      cout
          dfn[x]=low[x]=++ti;
          st.emplace(x);
          ins[x]=1;
          for(auto i:v[x])
          {
              if(!dfn[i])
              {
                  tarjan(i);
                  low[x]=min(low[x],low[i]);
              }
              else if(ins[i])
              {
                  low[x]=min(low[x],dfn[i]);
              }
          }
          if(low[x]==dfn[x])
          {
              ++cnt;
              while(1)
              {
                  int u=st.top();
                  st.pop();
                  ins[u]=0;
                  belong[u]=cnt;
                  b[cnt]+=a[u];
                  if(u==x)
                  {
                      break;
                  }
              }
          }
      }
      int topsort()//拓扑排序
      {
          for(int i=1;i
              if(!rd[i])
              {
                  q.emplace(i);
                  dis[i]=b[i];
              }
          }
          while(!q.empty())
          {
              int x=q.front();
              q.pop();
              for(auto i:vv[x])
              {
                  dis[i]=max(dis[i],dis[x]+b[i]);
                  rd[i]--;
                  if(!rd[i])
                  {
                      q.emplace(i);
                  }
              }
          }
          int ans=0;
          for(int i=1;i
              ans=max(ans,dis[i]);
          }
          return ans;
      }
      signed main()
      {
          cinnm;
          for(int i=1;i
              cina[i];
          }
          for(int i=1,x,y;i
              cinxy;
              v[x].emplace_back(y);
          }
          for(int i=1;i
              if(!dfn[i])
              {
                  tarjan(i);
              }
          }
          for(int i=1;i
              for(auto j:v[i])
              {
                  if(belong[i]!=belong[j]&&!mp[make_pair(belong[i],belong[j])])
                  //这里有时需要判重，有时又不需要，主要是看重边会不会有影响
                  //如果只是单纯跑拓扑是没有什么影响的，但如果要做与边相关的运算就有影响了
                  {
                      vv[belong[i]].emplace_back(belong[j]);
                      rd[belong[j]]++;
                      mp[make_pair(belong[i],belong[j])]=1;
                  }
              }
          }
          cout