有向图中在若两点之间可以互相到达，则称这两点强连通，如果一个点集内的所有点都可以互相到达，那么这个点集就是图的一个强连通分量，而我们需要找出有向图中的所有极大强连通分量，于是就用Tarjan算法进行强连通，并将一个连通块缩成一个点，这样就可以形成了一张有向无环图，对解题会很有帮助。
找强连通分量的方法就是 dfs 寻找某个点以及它的后继节点能够到达的最远祖先节点，如果这个最远祖先节点就是进入 dfs 的点，说明所有搜到的后继节点都是在这个强连通分量中，就依次将他们标记为同一个强连通分量。
head、point、nxt、size都是实现链式前向星的，开了两个，下标 0 是原图，下标 1 是缩点后的图。n 为总点数，t 是 dfs 的时间轴，用来记录dfs树中的先后访问顺序以及判断关于后继点到的最远祖先节点的标号。stx就是每个节点的在 dfs 时间轴上的标号，low 是每个节点能够通过其后继节点到达的最远的祖先节点，scc 是每个节点所属的强连通分量的编号，scccnt 是强连通分量的总个数。
主体是从大白书的模板上修改来的。
有注释：
1 #include//需要这些头文件 2 #include 3 #include 4 #include 5 using namespace std; 6 7 //maxn为点总数，maxm为边总数（原图） 8 const int maxn=100005; 9 const int maxm=200005;10 11 int head[2][maxn],point[2][maxm],nxt[2][maxm],size[2]; //0是原图，1是缩点后的图12 int n,t,scccnt; //n为点数，t是时间轴，scccnt是强连通分量数13 int stx[maxn],low[maxn],scc[maxn]; //stx是点的时间轴标号，low是能达到的最远祖先节点，scc是点所属强连通分量编号14 stack S; //用来存强连通分量内的点，并最后依次加入强连通分量15 16 void init(){ //原图的初始化17 memset(head,-1,sizeof(head));18 size[0]=size[1]=0;19 }20 21 void add(int a,int b,int c=0){ //加边函数，原图是0，建原图时可以不传入参数c，缩点图是122 point[c][size[c]]=b;23 nxt[c][size[c]]=head[c][a];24 head[c][a]=size[c]++;25 }26 27 void dfs(int s){28 stx[s]=low[s]=++t; //节点的时间轴标号，其能访问的起始最远祖先是它自己29 S.push(s); //将s点压入栈30 for(int i=head[0][s];~i;i=nxt[0][i]){31 int j=point[0][i];32 if(!stx[j]){ //如果j还没有被访问过，就说明不存在与之前已经定的强连通分量中，就从此点继续搜索33 dfs(j);34 low[s]=min(low[s],low[j]); //用后继点更新自己能到达的最远祖先35 }36 else if(!scc[j]){ //如果scc[j]已经有值，说明j已经是其他强连通分量中的点，那么对它 dfs 时没有搜索到s点说明s点和j点不在同一强连通分量中，所以不需要处理37 low[s]=min(low[s],stx[j]);38 }39 }40 if(low[s]==stx[s]){ //自己及后继能访问的最远祖先就是自己，那么从这之后的所有点都是这个强连通分量的点，从栈中取出点依次标记41 scccnt++;42 while(1){43 int u=S.top();S.pop();44 scc[u]=scccnt;45 if(s==u)break;46 }47 }48 }49 50 void setscc(){51 memset(stx,0,sizeof(stx));52 memset(scc,0,sizeof(scc));53 t=scccnt=0;54 for(int i=1;i<=n;++i)if(!stx[i])dfs(i); //依次dfs55 for(int i=1;i<=n;++i){56 for(int j=head[0][i];~j;j=nxt[0][j]){57 int k=point[0][j];58 if(scc[i]!=scc[k]){ //两点不在同一个强连通分量中，那么这两个强连通分量就继承两点的有向边。59 add(scc[i],scc[k],1);60 }61 }62 }63 }
木有注释：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn=100005; 8 const int maxm=200005; 9 10 int head[2][maxn],point[2][maxm],nxt[2][maxm],size[2];11 int n,t,scccnt;12 int stx[maxn],low[maxn],scc[maxn];13 stack S;14 15 void init(){16 memset(head,-1,sizeof(head));17 size[0]=size[1]=0;18 }19 20 void add(int a,int b,int c=0){21 point[c][size[c]]=b;22 nxt[c][size[c]]=head[c][a];23 head[c][a]=size[c]++;24 }25 26 void dfs(int s){27 stx[s]=low[s]=++t;28 S.push(s);29 for(int i=head[0][s];~i;i=nxt[0][i]){30 int j=point[0][i];31 if(!stx[j]){32 dfs(j);33 low[s]=min(low[s],low[j]);34 }35 else if(!scc[j]){36 low[s]=min(low[s],stx[j]);37 }38 }39 if(low[s]==stx[s]){40 scccnt++;41 while(1){42 int u=S.top();S.pop();43 scc[u]=scccnt;44 if(s==u)break;45 }46 }47 }48 49 void setscc(){50 memset(stx,0,sizeof(stx));51 memset(scc,0,sizeof(scc));52 t=scccnt=0;53 for(int i=1;i<=n;++i)if(!stx[i])dfs(i);54 for(int i=1;i<=n;++i){55 for(int j=head[0][i];~j;j=nxt[0][j]){56 int k=point[0][j];57 if(scc[i]!=scc[k]){58 add(scc[i],scc[k],1);59 }60 }61 }62 }