今天學習了強連通分量。
【參考博客】
如果覺得我講的有些地方難以理解或者存在問題（歡迎留言），可以看一下我借鑒的一些大佬的博客：
傳送門1 傳送門2
【知識儲備】
首先我們需要對幾個定義有一些概念：
強連通：有向圖中兩個點可以相互到達
強連通圖：有向圖中任意兩個點都是強連通的
強連通分量：一個有向圖的一個子圖中是強連通圖的最大的子圖就稱這個有向圖為強連通分量

通俗理解的話，強連通分量里面的任何兩個點都可以相互到達，也就是說至少存在一條路徑可以訪問到所有的點再回到起點（可以經過重復的點），就好像一個環，因此我們用DFS配合專門的算法來解決求連通分量的問題。

【算法介紹】
我們一般用Trajan算法解決相關問題。
正如上面的簡單分析，所謂的強連通分量，就是我們想要找一條可以回到起點的經過盡可能多點的路徑，那如何判斷我們是回到起點（或者已經訪問過的點）呢？我們就需要用數組進行標記每個點的狀態來方便我們進行判斷。
這里引入兩個關鍵的數組：
$DFN[MAXN]$ 用來標記DFS訪問到該點時的次序/時間
$LOW[MAXN]$ 用來儲存子樹（從這一點可以訪問到的點）中訪問時間最早的，初始化為DFN，也就是自身的訪問時間。如果訪問到了之前的點，就會變成前面的點的時間戳。

這樣對于之前的點來說就形成了一條從自身出發又回到自身的路徑，也就是一個強連通分量。

【算法實現】

對于每個點我們進行深搜，對每個點打上時間戳（給DFN和LOW賦值）

然后對每一個沒有訪問過的點直接進行 訪問，并且將LOW的值改為所有后面訪問點中最小的。
如果遇到一個訪問過的點

如果他不在棧中，就說明他和這個強連通分量沒有任何關系（在其他地方已經訪問結束，無法到這個點，無法形成回路，否則這個點肯定在棧中）。這里著重需要理解棧中保存的是已經訪問過的點中可以訪問到這個點的點（其他無關的點都已經彈出）

如果這個已經訪問的點在棧中（就比較開心，說明形成環了），如果這個點的最小的時間戳小于他就保存一下LOW，然后這個值就會回溯回去（有可能訪問的這個點在另一個小的強連通分量中，所以我覺得應該比較LOW，但是我看其他人的博客都是比較DFN，仔細想了一下覺得也可以，保存DFN的話也可以，但是我還是覺得比較LOW的話LOW的值就可以代表是否存在在同一個強連通分量中，更加優雅一些 。emm，如果覺得不能理解可以先往下看，不要在在意這些細節 ）。

最后DFS結束以后再回來看LOW的值是否改變，如果沒有改變說明這后面的所有點構成一個強連通分量，然后全部彈出（和他沒有關系的早早彈出去了，所以不用擔心后面的沒有關系的點怎么辦）

如果對一個點進行DFS改變LOW的值后LOW的值還沒有改變，仍然等于DFN，說明從這一個點出發是無法回到更早的點的，最早也就是自身，也就是說，他一定不是之前點的連通分量里面的（否則通過它肯定能夠訪問到之前的點，而之前的點的LOW都比較小），所以這個LOW沒有改變的點就是一個連通分量的根節點（比較慘的話就只有他一個節點，但也有可能他的子節點會訪問到他形成連通分量，但無論如何他都是根節點），我們不妨用一個棧保存訪問的順序，那么他后面訪問的點肯定都是他的連通分量中的點，全部彈出即可。（如果不是的話，后面的點肯定自成強連通分量，那么肯定更早彈出了）。 可能稍微有些懵，先有個概念然后再看代碼（注意是遞歸處理的，也就是訪問到后面處理完了再返回來處理前面）。

看著代碼理解一下吧，覺得哪里不能理解可以再看看上面的分析

void Trajan(int x)
{int v,tmp;DFN[x]=LOW[x]=++idx;	//賦給時間戳stack[++top]=x; vis[x]=true;for(int i=head[x];i;i=Edge[i].next){v=Edge[i].v;if(!DFN[v]){Trajan(v);if(LOW[v]<LOW[x]) LOW[x]=LOW[v];}else if(vis[v] && LOW[v]<LOW[x]){LOW[x]=LOW[v];}}if(DFN[x]==LOW[x]){cnt++;do{tmp=stack[top--];vis[tmp]=false;color[tmp]=cnt;}while (tmp!=x);}
}

【樣例題目】
Popular Cows

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.

Input

* Line 1: Two space-separated integers, N and M* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

*Line 1: A single integer that is the number of cows who are considered popular by every other cow.

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

題目大意：

有一群牛，他們相互崇拜，找出所有牛都崇拜的牛有多少

輸入：牛的個數n 崇拜的關系m,然后m行每行A,B,表示A崇拜B

輸出：被所有牛崇拜的牛的個數

【樣例分析】
將崇拜的關系變成一個有向圖，處于一個強連通分量里面的牛肯定是相互崇拜的，我們將一個強連通分量里面的所有牛看成一個點（染色），不同點重新形成一個圖，這個圖里面唯一的出度為0的點中牛的個數就是答案。
因為出度為0的點肯定是被其他點里的牛崇拜的，如果出度為0的點大于1的話兩個出度為0的點里面的牛是沒有辦法崇拜的，所以肯定不能被所有的牛崇拜，所以如果出度為0的點不止一個答案就是0，否則就是出度為0 的點里面牛的個數（出度為0的點肯定是大于等于1的，如果沒有出度為0 的點那么他們形成了一個環，而我們剛才說這是不同強連通分量，如果只有一個連通分量就只有一個點，也符合一個出度為0的點）

【AC代碼】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int MAXN=1e4+5;
const int MAXM=5e4+5;
struct node
{int v,next;
}Edge[MAXM];
int head[MAXN],tot;
int DFN[MAXN],LOW[MAXN];
int color[MAXN],cnt;
bool vis[MAXN];
int idx;
int stack[MAXN],top;
int OutDegree[MAXN];
int n,m;void init()
{memset(head,0,sizeof(head)); tot=0;idx=0; memset(vis,0,sizeof(vis));memset(DFN,0,sizeof(DFN));memset(color,0,sizeof(color));cnt=0; top=0;memset(OutDegree,0,sizeof(OutDegree));
}void read()
{int u,v;for(int i=0;i<m;i++){scanf("%d%d",&u,&v);tot++;Edge[tot].v=v; Edge[tot].next=head[u];head[u]=tot;}
}void Trajan(int x)
{int v,tmp;DFN[x]=LOW[x]=++idx;stack[++top]=x; vis[x]=true;for(int i=head[x];i;i=Edge[i].next){v=Edge[i].v;if(!DFN[v]){Trajan(v);if(LOW[v]<LOW[x]) LOW[x]=LOW[v];}else if(vis[v] && LOW[v]<LOW[x]){LOW[x]=LOW[v];}}if(DFN[x]==LOW[x]){cnt++;do{tmp=stack[top--];vis[tmp]=false;color[tmp]=cnt;}while (tmp!=x);}
}void solve()
{int v,mark,num,ans;for(int i=1;i<=n;i++){if(!DFN[i])Trajan(i);}for(int i=1;i<=n;i++){for(int j=head[i];j;j=Edge[j].next){v=Edge[j].v;if(color[i]!=color[v])OutDegree[color[i]]++;}}num=0; mark=-1;for(int i=1;i<=cnt;i++){if(!OutDegree[i]){num++; mark=i;}}ans=0;if(num!=1){printf("0\n");}else{for(int i=1;i<=n;i++){if(color[i]==mark){ans++;}}printf("%d\n",ans);}
}int main()
{while(~scanf("%d%d",&n,&m)){init();read();solve();}return 0;
}