Problem Address：http://poj.org/problem?id=1236
看题后觉得是和连通分支有很大关系的，也有关于入度和出度的。
所以上网搜了一下相关的知识。
借鉴了某个博客的解题报告：http://blog.csdn.net/xinghongduo/archive/2011/02/21/6197919.aspx
不过鉴于昨天发现对小规模数据用邻接矩阵的方法可以省时，所以今天也就用了邻接矩阵。
结果“盗用”的时候就犯了点小错误。
首先会用到的是Tarjan算法：http://wenku.baidu.com/view/ceb92fe2524de518964b7d66.html
百度文库的这篇文章简单易懂，非常适合学习~
用Tarjan算法可以计算出强连通分量的个数。
在此基础上，缩点（就是把一个强连通分量看成一个点），计算每个缩点的入度和出度。
缩点入度为0的个数就是第一问的答案。因为如果入度为0，说明没有其他的缩点可以到达这个缩点，所以这个缩点必须分配一个software。反之，如果有入度，则可以从别的缩点接收到这份software而不用自己使用一个。
缩点入度为0的个数和出度为0的个数的最大值就是第二问的答案。每个入度为0的点都必须有入度，每个出度为0的点也必须有出度，答案取决于其最大值。可以把缩点的组成看成一棵新的树，每个叶子结点表示出度为0的缩点，每个根结点表示入度为0的缩点。如果要使每个缩点都要有入度和出度，可以把出度为0的点连到入度为0的点。如果出度为0的大，则需要更多的从出度为0出来的线；反之，如果入度为0的大，则除了从出度为0连过来的线之外还需要额外的进入入度为0的线。所以答案是取决于两者的最大值。
以下贴代码：
由于坚持着代码的规范和整洁，代码再度冗长= =
而且不懂得粘贴上来，结果……
#include <iostream>using namespace std;bool map[105][105];int n,stack[105],top=0,dfn[105],low[105],index,pointnum,point[105];bool instack[105],flag[105][105];int out[105], in[105];void tarjan(int v){ int i; dfn[v] = index; low[v] = index; index++; instack[v] = true; stack[top]=v; top++; for (i=1; i<=n; i++) { if (map[v][i]) { if (!dfn[i]) { tarjan(i); if (low[i]<low[v]) low[v]=low[i]; } else if (instack[i] && low[i]<low[v]) low[v]=low[i]; } } if (dfn[v]==low[v]) { pointnum++; do { top--; i = stack[top]; instack[i] = false; point[i] = pointnum; }while(low[i]!=dfn[i]); }}int main(){ int i,j,x,a,b; while(scanf("%d", &n)!=EOF) { for (i=1; i<=n; i++) for (j=1; j<=n; j++) map[i][j] = false; for (i=1; i<=n; i++) { while(scanf("%d", &x)) { if (x==0) break; map[i][x] = true; } } for (i=1; i<=n; i++) { dfn[i] = 0; low[i] = 0; instack[i] = false; } index = 1; top = 0; pointnum = 0; for (i=1; i<=n; i++) { if (!dfn[i]) tarjan(i); } for (i=1; i<=pointnum; i++) for (j=1; j<=pointnum; j++) flag[i][j] = true; for (i=1; i<=pointnum; i++) { out[i] = 0; in[i] = 0; } for (i=1; i<=n; i++) { for (j=1; j<=n; j++) { if (map[i][j]) { if (point[i]!=point[j] && flag[point[i]][point[j]]) { out[point[i]]++; in[point[j]]++; flag[point[i]][point[j]] = false; } } } } for (a=0,b=0,i=1; i<=pointnum; i++) { if (!in[i]) a++; if (!out[i]) b++; } printf("%d/n", a); if (pointnum>1) { if (b>a) printf("%d/n", b); else printf("%d/n", a); } else printf("0/n"); } return 0;}
p.s.每天学算法确实辛苦……加油！
