1.强连通分量：
强连通分量可以理解为边数最少的情况下是一个环。
这里写了一个模板题用的是tarjan算法，当然还有其他算法。
tarjan算法的关键其实还是对于num数组和low数组的使用
然后可以用栈来分离不同的ssc
感觉跟双边连通分量有异曲同工之妙

第一题hdu1296

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn  20010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n,m;
vector < vector<int> > maps;
int low[maxn];
int num[maxn];
int stacks[maxn],ssc[maxn];
int dfsnum=0,top,cnt;
void init(){memset(low,0,sizeof(low));memset(num,0,sizeof(num));memset(ssc,0,sizeof(ssc));dfsnum=0;top=0;cnt=0;
}
void dfs(int u){stacks[top++]=u;low[u]=num[u]=++dfsnum;for(int i=0;i<maps[u].size();i++){int v=maps[u][i];if(!num[v]){dfs(v);low[u]=min(low[v],low[u]);}else if(!ssc[v])  low[u]=min(low[u],num[v]);  //处理回退边}if(low[u]==num[u]){   //栈底的点是ssc的祖先，low=num值cnt++;while(true){int v=stacks[--top];ssc[v]=cnt;if(u==v)  break;}}
}void tarjan(){init();for(int i=1;i<=n;i++)   //因为最少便的情况下是一个环，所以说从哪个点开始走，都可以回到原始点if(!num[i])  dfs(i);
}int main()
{while(scanf("%d%d",&n,&m)&&n){init();maps.clear();maps.resize(10010);for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);maps[x].push_back(y);}tarjan();if(cnt>1)  printf("No\n");else printf("Yes\n");}return 0;
}

第二题hdu1827
这个还是先用tarjan算法来求有多少个强连通分量，然后我们再用缩点的思想把一个强连通量当一个点来看，因为要最少的人，相当于找入度0的人来打电话。

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn  2010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n,m;
vector < vector<int> > maps;
int low[maxn];
int num[maxn];
int stacks[maxn],ssc[maxn];
int dfsnum=0,top,cnt;
int price[maxn];
int cost[maxn];
int degree[maxn];
void init(){memset(low,0,sizeof(low));memset(num,0,sizeof(num));memset(ssc,0,sizeof(ssc));memset(degree,0,sizeof(degree));memset(cost,MaxN,sizeof(cost));dfsnum=0;top=0;cnt=0;
}
void dfs(int u){stacks[top++]=u;low[u]=num[u]=++dfsnum;for(int i=0;i<maps[u].size();i++){int v=maps[u][i];if(!num[v]){dfs(v);low[u]=min(low[v],low[u]);}else if(!ssc[v])  low[u]=min(low[u],num[v]);}if(low[u]==num[u]){cnt++;while(true){int v=stacks[--top];ssc[v]=cnt;cost[cnt]=min(cost[cnt],price[v]);if(u==v)  break;}}
}
void tarjan(){for(int i=1;i<=n;i++)if(!num[i]){dfs(i);}for(int i=1;i<=n;i++){for(int f=0;f<maps[i].size();f++){if(ssc[i]!=ssc[maps[i][f]])  degree[ssc[maps[i][f]]]++;}}int ans1=0,ans2=0;//for(int i=1;i<=n;i++)  cout<<degree[i]<<" ";for(int i=1;i<=cnt;i++){if(degree[i]==0)  ans2+=cost[i],ans1++;}printf("%d %d\n",ans1,ans2);
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){init();maps.clear();maps.resize(1010);for(int i=1;i<=n;i++)  scanf("%d",&price[i]);for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);maps[x].push_back(y);}tarjan();}return 0;
}