题目链接：http://uoj.ac/problem/146
求强连通分量的个数 。
1.有向图中：
强连通：两个节点可以互相到达
强连通图：图中的任意两点都可以互相到达也即任意两点都是强连通
强连通分量：图中的子图是强连通图
2.Tarjan算法：用来求有向图的强连通分量。基于DFS算法，每个强连通分量为搜索树中的一颗子树。
搜索时，把当前图中未处理的点加入一个堆栈，回溯时可以栈顶到栈中的节点是否为强连通分量。
DFN[u]为节点u搜索的次序编号（时间戳）
LOW[u]为u或u的子树能到最早的节点的次序号
当DFN[u]==LOW[u]时，以u为根的搜索树上所有节点是一个强连通分量。
运行tarjan的过程中，每个顶点被访问了一次，且只进出一次堆栈，每条边也只被放过一次，所以时间复杂度为O（N+M).
代码如下:
#include<bits/stdc++.h> using namespace std; const int maxn = 200010; vector<int>E[maxn]; int n,dfn[maxn], vis[maxn],low[maxn], tot = 0, ans=maxn; stack<int >S; void tarjan(int x) { low[x] = dfn[x] = ++tot; S.push(x),vis[x]=1; for (int i = 0;i < E[x].size();i++) { int v = E[x][i]; if (!dfn[v]) { tarjan(v); low[x] = min(low[x], low[v]); } else if (vis[v]) { low[x] = min(low[x], dfn[v]); } } if (low[x] == dfn[x]) { int cnt = 0; while (1) { int now = S.top(); S.pop(); vis[now] = 0; cnt++; if (now == x)break; } if (cnt > 1) ans = min(ans, cnt); } } int main() { cin >> n; for (int i = 1;i <= n;i++) { int x; scanf("%d", &x); E[i].push_back(x); } for (int i = 1;i <= n;i++) { if(!dfn[i]) tarjan(i); } cout << ans << endl; return 0; }
