1、略2、计算有向无圈图的根输入一个有向无圈图DAG，计算和输出DAG的根r（即r到其他任何顶点都有一条路。
若图中没有根，则输出“not found”）。
输入：顶点数n和边数e;以下为e行，每行为一条有向边的两个端点输出：根r或者“not found”算法分析设const mx=100;{顶点数的上限}varn,e,i,j,k,a,b:integer;{ 顶点数n、边数e}g:array[1..mx,1..mx]of boolean;{传递闭包}bn:boolean;{根存在标志}1、输入信息，计算传递闭包readln(n,e);{输入顶点数和边数}fillchar(g,sizeof(g),0);{ 有向无圈图初始化}for i:=1 to e do{输入信息，构造传递闭包的初始值}begin readln(a,b);g[a,b]:=true end;for k:=1 to n do{计算传递闭包}for i:=1 to n dofor j:=1 to n doif g[i,j] or g[i,k] and g[k,j]then g[i,j]:=true;2、计算DAG的根然后枚举每一个顶点。
根据传递闭包的信息，若当前顶点至其它所有顶点有路，则判定该顶点即为根。
若没有一个顶点可作为DAG的根，则输出失败信息for i:=1 to n do{枚举每一个可能的根}beginbn:=true;{设定I至其他所有顶点有路的标志}for j:=1 to n do{若I至任一个顶点无路，则返回bn为false}if (i<>j) and not g[i,j]then begin bn:=false; break end;if bn then break{若I至其他所有顶点有路，则输出根i}end;if bn then writeln(i)else writeln('not found'){若不存在根，则输出失败信息}3、寻找满足条件的连通分支输入一张顶点带权的无向图，分别计算含顶点数最多的一个连通分支和顶点的权之和最大的一个连通分支。
输入：n（顶点数，1<=n<=20）以下n行，依次表示顶点1 ~ 顶点n上的权；e（边数，1<=e<=210）以下e行，每行为有边连接的一对顶点。
输出：两行，一行为含顶点数最多的一个连通分支，一行为顶点的权之和最大的一个连通分支，输出时按顶点编号从小到大输出。
[问题分析]通过longlink计算出每个顶点所在的连通分支，然后在所有可能的连通分支中找出满足条件的解。
至于计算连通分支的顶点方案也不难，只要分别从连通分支中任选一个代表顶点，由此出发，通过深度优先搜索即可得到顶点方案。
设best，besti—含顶点数最多的连通分支中的顶点数和代表顶点；max,maxk——顶点的权和最大的连通分支的顶点权和和代表顶点计算best,besti,max,maxk的过程如下：1、读入无向图的信息；2、计算传递闭包longlink；3、穷举每一个顶点for I:=1 to n dobegink:=0;s:=0for j:=1 to n do{计算顶点i所在连通分支中的顶点总数k和顶点的权之和s} if longlink[i,j] then begininc(k);inc(s,顶点j的权)end;if k>best then begin best:=k;besti:=I end;{若k为目前最大，则记入best,i 作为代表顶点记入besti}if s>max then begin max:=s;maxk:=I end;{若s为目前最大，则记入max,i 作为代表顶点记入maxk} if k=n then break; {若整个图是连通图，则退出}end;4、dfs(besti); {从代表顶点besti出发，深度优先搜索含顶点数最多的连通分支}5、dfs(maxk); {从代表顶点maxk出发，深度优先搜索顶点的权之和最大的连通分支}显然，以上算法的时间复杂度为O（n*n）。
[参考程序]program ex3;const maxn=20;varw:array[1..maxn] of longint;link,longlink:array[1..maxn,1..maxn] of boolean;out:array[1..maxn] of boolean;n,e,i,j,k,s,x,y,best,besti,max,maxk:longint;procedure dfs(k:longint);var i:longint;beginfor i:=1 to n doif (longlink[k,i])and(not out[i]) thenbeginout[i]:=true;dfs(i);end;end;beginread(n);for i:=1 to n do read(w[i]);read(e);fillchar(link,sizeof(link),false);for i:=1 to e dobeginread(x,y);link[x,y]:=true;link[y,x]:=true;end;longlink:=link;for k:=1 to n dofor i:=1 to n dofor j:=1 to n dolonglink[i,j]:=longlink[i,j] or longlink[i,k] and longlink[k,j]; best:=1; besti:=1;max:=w[1]; maxk:=1;for i:=1 to n dobegink:=0;s:=0;for j:=1 to n doif longlink[i,j] thenbegininc(k);inc(s,w[i])end;if k>best then begin best:=k;besti:=i; end; if s>max then begin max:=s;maxk:=i; end;if k=n then break;end;fillchar(out,sizeof(out),false);out[besti]:=true;dfs(besti);for i:=1 to n doif out[i] then write(i,' ');writeln;fillchar(out,sizeof(out),false);out[maxk]:=true;dfs(maxk);for i:=1 to n doif out[i] then write(i,' ');writeln;end.输入:534581051 21 32 53 44 5输出:1 2 53 4 54、计算DAG中的最长路输入一个有向无圈图DAG，计算和输出DAG中最长路的长度输入：顶点数n和边数e；以下为e行，每行为一条有向边的两个端点和边权输出：最长路的长度算法分析设constmax=100;{顶点数的上限}maxint=10000;varn,e,i,j,k,a,b,ans:integer;{顶点数n、边数e }g:array[1..max,1..max]of integer;{g[I,j]为顶点I至顶点j的路径长度}1、输入有向无圈图的信息首先输入有向无圈图的信息。
若顶点I至顶点j有边，则g[I,j]设为wij；否则g[I,j]设为-∞。
readln(n,e);{输入输入顶点数和边数}fillchar(g,sizeof(g),0);{最长路径长度矩阵初始化for i:=1 to e do{输入边信息，构造最长路径长度矩阵的初始值}begin readln(a,b, wab ); g[a,b]:= wabend;for i:=1 to n do{将最长路径长度矩阵中无边的元素设为-∞}for j:=1 to n doif (i<>j)and(g[i,j]=0) then g[i,j]:=-maxint;2、按照计算传递闭包的思想计算每一对顶点间的最长路，找出最长路径长度for k:=1 to n do{计算最长路径长度矩阵}for i:=1 to n dofor j:=1 to n doif g[i,k]+g[k,j]>g[i,j]then g[i,j]:=g[i,k]+g[k,j];ans:=0;{ 最长路径长度初始化}for i:=1 to n do{枚举所有可能的顶点对，将其中的最大g值找出来}for j:=1 to n doif g[i,j]>ans then ans:=g[i,j];{调整最长路径长度}writeln(ans){输出最长路径长度}5、计算带权有向图的中心输入一个带权有向图G ，计算和输出G 的中心v(v 是G 的一个顶点，v 的偏心距定义为输入：顶点数n 和边数e ；以下为e 行，每行为一条有向边的两个端点和边权输出：G 的中心v算法分析const mx=100;varn,e,i,j,k,a,b,ans:integer;{ 顶点数为n ，边数为e ，中心为ans}w,bt,b0:real;{bt 为所有顶点偏心距的最小值，b0为当前顶点的偏心距}g:array[1..mx,1..mx]of real;{最短路长矩阵。
初始时g[i,i]=0,g[I,j]=计算后，g[i,j]存储顶点I 至顶点j 的最短路长}1、 输入信息，构造最短路长矩阵greadln(n,e);{输入顶点数和边数}for i:=1 to n do{输入信息，构造最短路长矩阵g 的初始值}for j:=1 to n doif i<>j then g[i,j]:=maxintelse g[i,j]:=0;for i:=1 to e dobegin readln(a,b,w);g[a,b]:=w;end;for k:=1 to n do{计算任一对顶点间的最短路长}for i:=1 to n dofor j:=1 to n doifg[i,k]+g[k,j]<g[i,j]then g[i,j]:=g[i,k]+g[k,j];2、 计算图的中心依次计算每一个顶点i 的偏心距b0。
每计算一个顶点的偏心距b0，调整所有顶点偏心距的最小值和图的中心（即顶点I 的偏心距b0小于所有顶点偏心距的最小值bt ，则bt 设为b0，图的中心ans 设为i ）。
依次类推，直至所有顶点的偏心距计算完为止。
此时的ans 即为问题的解bt:=maxint; ans:=0;{所有顶点偏心距的最小值和图的中心初始化}for i:=1 to n dobegin }{max 的最短路长到从v w V w )的中心为中偏心距最小的顶点称G Gb0:=0;{顶点I的偏心距初始化}for j:=1 to n do if g[i,j]>b0 then b0:=g[i,j];{计算顶点I的偏心距}if b0<bt{若顶点I的偏心距为目前最小，则记下，并将顶点I设为图的中心}then begin bt:=b0; ans:=i endend;writeln(ans){输出图的中心}6、snow问题描述：随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。