强连通图

什么是强连通图？

强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每
一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有
向图中的极大强连通子图称做有向图的强连通分量

DFS序

在这里插入图片描述

Kosaraju算法

在这里插入图片描述

默默地感叹一句：TA的PPT实在是写得太好了！！！

例：班长竞选

大学班级选班长，N 个同学均可以发表意见

若意见为 A B 则表示 A 认为 B 合适，意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适

勤劳的 TT 收集了M条意见，想要知道最高票数，并给出一份候选人名单，即所有得票最多的同学，你能帮帮他吗？

Input

本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。

Output

对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。

接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！

Sample Input

24 33 22 02 13 31 02 10 2

Output

Case 1: 2

0 1

Case 2: 2

0 1 2

题解：A认为B合适，链接一条有向边A→B，B→C，有A→C，满足传递关系实则我们可以把它视为一个强连通图问题，支持A的人就等于能够达到A点的点和可以到达能够到达A点的点的点所在的强连通分量（这句话有点拗口我画幅图理解吧

在这里插入图片描述

由上图可以知道1是得到2和3支持的，但是3又是被5支持的，而5所在
的强连通分量，5是被4，7，6支持的，故因为传递性，所以1也会得到
5，4，6，7的支持

Codes

#include
   
    #include
    
     #include
     
      using namespace std;const int maxn=1e5;int t,n,m,a,b,scnt,dcnt;//t测试组数，n个点，m条边,scnt,dcnt计数第几次访问 int vis[maxn],scn[maxn],scc[maxn],sc[maxn],c[maxn],dfn[maxn];//dfn-dfs后序列第i个点 //vis-是否访问过，c[i]i号点所在scc编号 vector
      
        G1[maxn],G2[maxn],G3[maxn],G4[maxn];//原图，反图 ,入度为0的点图，最后关系图void Init(){
   //疯狂初始化  for(int i=0;i
       
        =1;i--){
     if(c[dfn[i]]==0){
      ++scnt;   dfs2(dfn[i]);  } }}int main(){
    ios::sync_with_stdio(false); cin>>t;//组数  for(int j=1;j<=t;j++){
     Init();//初始化   cin>>n>>m;  for(int i=0;i
        
         >a>>b; G1[a].push_back(b);//原图 G2[b].push_back(a);//构造反图 }//反图的SCC和原图的SCC是相同的 kosaraju();//求出联通分量 for(int i=0;i