时隔好久，重新把那些题找出来，写一写了，毕竟实力还很有限，得学。
一开始，最大的疑惑还是怕一个环里有另外一个环（毕竟经验不丰富），后来看到了这段话
T2 信息传递
大意：在一个只有n条有向边的图中，每个结点出度为1，求一个包含节点数最少的环。
分析：因为只有n条边并且每个点都有且仅有一条边连出去，所以只可能存在简单环，不会出现那种8字形的环套环。
证明：每个点有两种情况：1.不在任何一个环中 这样的点可以直接忽略掉，看成是有n-1个点,n-1条边来证明就行了。2.在某个环中。那么如果我们现在有了一个圈圈形状的环，大小为k，那么每一个点都应该入度出度都为1，这样的环只存在一个回路，也就是一个简单环，如果存在多个回路，那么应该存在某个点的入度>1，但是又要保证别的点出度至少为1，所以出度之和应该是>k的，但入度之和=k，无法满足，所以不存在某个环存在两条或以上数量的回路。证毕。
满足了这样的性质，tarjan或者O(n)扫描都是可以解决本题的。
恍然大悟，既然弱，就多积累吧！
不过，也据说“这题我觉得，真的，画图是关键（我记得我以前的竞赛老师王老师经常说的一件事情就是数形结合），多画图，多模拟，就很容易找到需要解决问题的方法。”。觉得也挺有道理的，发现自己很多时候都是引用别人现成的，属于自己的本质的想法会比较少。
另附，网上好像还有其他的做法，比如并查集法，还有一种把入度为0的点删去后，再dfs查找的。先给出后者的代码。
即用类似拓扑的方式把所有入度为0的点踢掉，然后可以保证剩下的每个点都在一个有向环中,同时这个图特殊的建法好像可以保证任意两个环之间没有公共点...用on的时间扫一遍就可以了
1 #include2 #include 3 #define rep(i,j,k) for(int i = j; i <= k; i++) 4 #define maxn 200009 5 using namespace std; 6 int next[maxn] = { 0}; 7 bool used[maxn] = { 0}; 8 int num[maxn] = { 0}, ans = 0xfffffff; 9 10 int read()11 {12 int s = 0, t = 1;13 char c = getchar();14 while( !isdigit(c) ){15 if( c == '-' ) t = -1;16 c = getchar();17 }18 while( isdigit(c) ){19 s = s * 10 + c - '0';20 c = getchar();21 }22 return s * t;23 }24 25 void dfs(int x)26 {27 used[x] = 1;28 num[next[x]]--;29 if( !num[next[x]] ) dfs(next[x]);30 }31 32 void search(int x,int num)33 {34 used[x] = 1;35 if( !used[next[x]] ){36 search(next[x],num+1);37 }38 else if( num != 1 ) ans = min(num,ans);39 }40 41 int main()42 {43 int n = read();44 rep(i,1,n){45 next[i] = read();46 num[next[i]]++;47 }48 rep(i,1,n){49 if( !num[i] && !used[i] ) dfs( i );50 }51 rep(i,1,n){52 if( !used[i] )53 search(i,1);54 }55 if( ans > n ) cout<<0<
接下来，写求强连通块的算法。使用两次dfs的。这个算法在codevs上跑的时间比上面的多一些（但这个求完强连通分量后，还能得到原图的拓扑排序）。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define maxn 200009 7 #define rep(i,j,k) for(int i = j; i <= k; i++) 8 using namespace std; 9 10 bool used[maxn] = { 0};11 int next[maxn] = { 0};12 vector q[maxn];13 stack s;14 int ans = 0xfffffff;15 16 int read()17 {18 int s = 0, t = 1;19 char c = getchar();20 while( !isdigit(c) ){21 if( c == '-' ) t = -1;22 c = getchar();23 }24 while( isdigit(c) ){25 s = s * 10 + c - '0';26 c = getchar();27 }28 return s * t;29 }30 31 void dfs(int i)32 {33 used[i] = 1;34 if( !used[next[i]] ) dfs(next[i]); 35 s.push(i); //注意到最后才把这个元素压入栈。 36 }37 38 int search(int x)39 {40 used[x] = 1;41 int s = q[x].size();42 int ans = 1;43 rep(i,0,s-1){44 if( !used[q[x][i]] )45 ans += search(q[x][i]);46 }47 return ans;48 }49 50 int main()51 {52 int n = read();53 rep(i,1,n){54 next[i] = read();55 q[next[i]].push_back(i);56 }57 rep(i,1,n){58 if( !used[i] ) dfs(i);59 }60 memset(used,0,sizeof(used));61 rep(i,1,n){62 int m = s.top(), k = 0; s.pop();63 if( !used[m] ){64 k = search(m); //注意当 k = 1 时应舍去。65 if( k <= 1 ) continue;66 else ans = min(k,ans);67 }68 }69 cout< <
接下来是tarjan算法求强连通块。这个算法也要比上面第二种快一点。
#include#include #include #define maxn 200009#define rep(i,j,k) for(int i = j; i <= k; i++)using namespace std;int pre[maxn] = { 0};int low[maxn] = { 0};int next[maxn] = { 0}; int sccno[maxn] = { 0};bool used[maxn] = { 0};int ans = 0xfffffff, cnt = 0;int sccno_cnt = 0;stack s;int read(){ int s = 0, t = 1; char c = getchar(); while( !isdigit(c) ){ if( c == '-' ) t = -1; c = getchar(); } while( isdigit(c) ){ s = s * 10 + c - '0'; c = getchar(); } return s * t;}void dfs(int now){ pre[now] = low[now] = ++cnt; used[now] = 1; s.push(now); if( used[next[now]] ){ low[now] = min(pre[next[now]],low[now]); } else if( !sccno[next[now]] ) { dfs(next[now]); low[now] = min(low[now],low[next[now]]); } if( pre[now] == low[now] ){ int num = 0; int t = s.top(); sccno_cnt++; while( t != now ){ sccno[t] = sccno_cnt; t = s.top(); s.pop(); num++; } if( num <= 1 ) return; else ans = min(ans,num); }}int main(){ int n = read(); rep(i,1,n){ next[i] = read(); } rep(i,1,n){ if( !used[i] ){ dfs(i); } } cout< <
就这样，求强连通分量的两种常见算法都打了，而且还有针对此题的一种算法。加油！最后说一句，如果把STL的栈改成手打的一个数组，效率会提高一些；可能有几毫秒的提升；不过我也不敢下断言，毕竟比较弱。
总结，根据codevs和vijos的数据显示，第一个算法跑的时间最短，效率最高（两个网站都能AC），其次是第三个算法（codevs能AC，vijos最后一个点就判了运行错误，其他的点都A了）；最差的是第二个算法(codevs能AC，但vijos上只能过两个点，也有可能是我水平有限，无法进一步优化）。
加油，明天会更好。