链接：click here
题意：
校园网络
时间限制：3000 ms | 内存限制：65535 KB
难度：5
描述
南阳理工学院共有M个系，分别编号1~M,其中各个系之间达成有一定的协议，如果某系有新软件可用时，该系将允许一些其它的系复制并使用该软件。但该允许关系是单向的，即：A系允许B系使用A的软件时，B未必一定允许A使用B的软件。
现在，请你写一个程序，，根据各个系之间达成的协议情况，计算出最少需要添加多少个两系之间的这种允许关系，才能使任何一个系有软件使用的时候，其它所有系也都有软件可用。
输入第一行输入一个整数T，表示测试数据的组数(T<10)每组测试数据的第一行是一个整数M，表示共有M个系(2<=M<=100)。随后的M行，每行都有一些整数，其中的第i行表示系i允许这几个系复制并使用系i的软件。每行结尾都是一个0，表示本行输入结束。如果某个系不允许其它任何系使用该系软件，则本行只有一个0.输出 对于每组测试数据，输出最少需要添加的这种允许关系的个数。 样例输入 152 4 3 04 5 0001 0样例输出2这道题第一感觉和图的入度出度有关，最后写了一下，数据比较水。
思路： 统计入度和出度就行了，一个顶点既有出度也有入度就表示此顶点不需要添加线路，最后取最大值比较即可。
代码：
#include <math.h>#include <queue>#include <deque>#include <vector>#include <stack>#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>using namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);static const int INF = ~0U >> 2;static const int MAXN = 102;int mapp[MAXN][MAXN],comeder[MAXN],outder[MAXN];int n,m,i,j,cas,cnt;void input(){for(i=1; i<=n; i++)while(~scanf("%d",&m),m){mapp[i][m]=1;}for(i=1; i<=n; i++)for(j=1; j<=n; j++){if(mapp[i][j]){comeder[j]=1;outder[i]=1;}}}void output(){int sum1=0,sum2=0;for(i=1; i<=n; i++){if(comeder[i]==0)sum1++;if(outder[i]==0)sum2++;}printf("%d\n",Max(sum1,sum2));}int main(){scanf("%d",&cas);while(cas–){int sum;scanf("%d",&n);mem(mapp,0),mem(comeder,0),mem(outder,0);input();output();}return 0;}后来看下题解，原来是强连通缩点targan算法，强连通缩点还没有学习，先贴上别人已过的代码，研究~~
解析（转）：点击打开链接 Tarjan算法详解 【功能】 Tarjan算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。 【算法思想】 用dfs遍历G中的每个顶点，通dfn[i]表示dfs时达到顶点i的时间，low[i]表示i所能直接或间接达到时间最小的顶点。(实际操作中low[i]不一定最小，但不会影响程序的最终结果) 程序开始时，order初始化为0，在dfs遍历到v时，low[v]=dfn[v]=order++，v入栈（这里的栈不是dfs的递归时系统弄出来的栈）扫描一遍v所能直接达到的顶点k，如果 k没有被访问过那么先dfs遍历k，low[v]=min(low[v],low[k])；如果k在栈里，那么low[v]=min(low[v],dfn[k])(就是这里使得low[v]不一定最小，但不会影响到这里的low[v]会小于dfn[v])。扫描完所有的k以后，如果low[v]=dfn[v]时，栈里v以及v以上的顶点全部出栈，且刚刚出栈的就是一个极大强连通分量。 【大概的证明】 1． 在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，low[v]=dfn[v]时，v一定能到达栈里v上面的顶点： 因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有low=dfn），这时如果发现low[v]=dfn[v]，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。 2 .dfs遍历时，如果已经遍历完v所能直接到达的顶点而low[v]=dfn[v]，我们知道v一定能到达栈里v上面的顶点，这些顶点的low一定小于 自己的dfn，不然就会出栈了，也不会小于dfn[v],不然low [v]一定小于dfn[v],所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话low[v]也一定小于dfn[v]（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。 【时间复杂度】 因为所有的点都刚好进过一次栈，所有的边都访问的过一次，所以时间复杂度为O（n+m） 代码如下：
// 强连通分量缩点#include <iostream>#include <cstring>#include <cstdio>#include <stack>using namespace std;const int MAX = 105;int map[MAX][MAX];int low[MAX], DFN[MAX], IN[MAX], OUT[MAX], instack[MAX], t[MAX];int n, order, res, ans;stack<int> S;void init(){memset(map, 0, sizeof(map));memset(low, 0, sizeof(low));memset(DFN, 0, sizeof(DFN));memset(IN, 0, sizeof(IN));memset(OUT, 0, sizeof(OUT));memset(instack, 0, sizeof(instack));memset(t, 0, sizeof(t));while(!S.empty())S.pop();res = 0;order = 0;}int min(int x, int y){return x < y ? x : y;}void tr(int u){int v;DFN[u] = low[u] = ++order;instack[u] = 1;S.push(u);for (int i = 1; i <= n; i++){if(map[u][i]){if(!DFN[i]){tr(i);low[u] = min(low[u], low[i]);}else if(instack[i])low[u] = min(low[u], DFN[i]);}}if(DFN[u] == low[u]){++res; // res 代表强连通分量的个数do{v=S.top();S.pop();instack[v] = 0;t[v] = res;}while(v != u);}}void tarjan(){for (int i = 1; i <= n; i++)if(!DFN[i])tr(i);}void solve(){for (int i = 1;i <= n; i++){for (int j = 1;j <= n; j++)if(map[i][j]) // 统计每个强连通分量缩点的入度和出度{++IN[t[i]];++OUT[t[j]];}}int xx, yy;xx = yy = 0;for(int i = 1; i <= res; i++){if(IN[i]==0)xx++;else if(OUT[i]==0)yy++;}ans = xx > yy ? xx : yy; // 结果为缩点后的有向图中出度为0或者入度为0中的大者}int main(){int T, x;scanf("%d", &T);while (T–){init();scanf("%d",&n);for (int i = 1; i <= n; i++){while (scanf("%d", &x), x)map[i][x] = 1;}tarjan();solve();if(res == 1)printf("0\n");elseprintf("%d\n", ans);}return 0;}
那段岁月，无论从何种角度读你，你都完美无缺，
