http://www.codeforces.com/problemset/problem/698/B
很不错的题目。不难但是需要一点思维和严谨。
一个n条边的有向图，每个点都只有一条出边，要求修改最少点数的出边，使得整个图变成一个有根树（根节点的出边指向自己）。方案任意。n<=200000
首先看这个图是什么样子的。
首先可能有好几个连通块。
对于每个连通块：有n个点n条边，所以把边看成无向边的话一定有一个环（自环或不是自环）。而且这个环一定是一个指向下一个，是一个强连通分量，
不可能出现图二那种情况。
这一个环上所有点的出度全都用上了，所以如果有其他点和它们连着的话，一定是指向这个环。
所以这是一颗基环内向树。如下图1
| 
图1 图2
找环的工作用tarjan就好了。找到所有环之后，就要构造一棵树了。
我们的思路是先找到一个根，然后把所有其他连通块的环，易证需要且只需要取其中任意一个结点，将其指向根即可。
首先，如果有自环的话，随意取一个当作根即可（因为由构造方法可知取哪一个并不影响最终改变的出边的数量）。
否则，任取一个大环，任取其中一个结点作根即可，不过答案要加1.
再将其余连通块按方法构造即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 #include <vector> 8 using namespace std; 9 10 const int N = 200010; 11 int tot,top,n,color; 12 int a[N],dfn[N],low[N],stack[N],c[N],size[N]; 13 bool v[N],flag[N]; 14 vector<int> cmem[N]; 15 16 void tarjan(int x) 17 { 18 low[x] = dfn[x] = ++tot; 19 stack[++top] = x; 20 v[x] = 1; 21 int y = a[x]; 22 if(!dfn[y]) { 23 tarjan(y); 24 low[x] = min(low[x], low[y]); 25 } 26 else if(v[y]) 27 low[x] = min(low[x], dfn[y]); 28 29 if(dfn[x]==low[x]) { 30 color++; 31 int temp; 32 do { 33 temp = stack[top--]; 34 c[temp] = color; 35 v[temp] = 0; 36 size[color]++; 37 cmem[color].push_back(temp); 38 } while(temp!=x); 39 } 40 } 41 42 int main() 43 { 44 int i,root = 0,ans = 0; 45 cin >> n; 46 for(i = 1; i<=n; i++) { 47 scanf("%d", &a[i]); 48 } 49 for(i = 1; i<=n; i++) 50 if(!dfn[i]) tarjan(i); 51 for(i = 1; i<=n; i++) { 52 int y = a[i]; 53 if(c[y]!=c[i]) 54 flag[c[i]] = 1; 55 } 56 for(i = 1; i<=color; i++) 57 if(!flag[i]) { 58 if(size[i]==1) root = cmem[i][0]; 59 } 60 if(!root) { 61 ans++; 62 for(i = 1; i<=color; i++) 63 if(!flag[i]) { 64 root = cmem[i][0]; 65 a[cmem[i][0]] = cmem[i][0]; 66 break; 67 } 68 } 69 for(i = 1; i<=color; i++) 70 if(!flag[i] && cmem[i][0]!=root) { 71 ans++; 72 a[cmem[i][0]] = root; 73 } 74 printf("%d ", ans); 75 for(i = 1; i<=n; i++) 76 printf("%d ", a[i]); 77 return 0; 78 }