图的应用简约.ppt

数据结构 var a,b,head,next,point,color:array[0..2001]of longint; /*初始序列为a（对应q1），后缀的最小值序列为b，其中b[i]= ；邻接表的表首顶点为head，后继指针为next，顶点序列为point，顶点的涂色序列为color*/ s:array[1..2,0..1000]of longint; /*s[1]栈，栈首指针为s[1,0];s[2]栈, 栈首指针为s[2,0]*/ n,p,i,j,last:longint; /*序列长度为n，当前应取数字为last*/ proc bad}; /*输出失败信息*/ { writeln(0);close(output);halt }/* bad} */ proc addedge(a,b:longint); /*（a,b）进入邻接表*/ var t:longint; { inc(p);point[p]←b; /*增加顶点b*/ if head[a]=0 /*（a,b）进入邻接表*/ then head[a]←p else{ t←head[a]; while next[t]0 do t←next[t]; next[t]←p };/*else*/ };/* bad} */ 顶点涂色 proc dfs(now:longint); var t:longint; {t←head[now]; /*搜索与顶点now相邻的所有顶点*/ while t0 do { if color[point[t]]=0 /*若顶点now相邻的顶点point[t]未涂色，则该顶点涂互补色，沿该顶点递归下去*/ then{ color[point[t]]←3-color[now]; dfs(point[t])};/*then*/ if color[point[t]]=color[now] /*若顶点now与相邻顶点point[t]涂相同色，则失败退出*/ then bad}; t←next[t]; /*访问与顶点now相邻的下一个顶点*/ };/*while*/ };/*dfs*/ 构造二分图 { assign(input,twostack.in);reset(input); /*输入文件读准备*/ assign(output,twostack.out);rewrite(output); /*输出文件写准备*/ fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0); /*两栈空*/ readln(n); /*读入排列*/ for i←1 to n do read(a[i]); b[n+1]←maxlongint;p←0; for i←n downto 1 do /*计算b[i]= */ { b[i]←b[i+1]; if a[i]b[i] then b[i]←a[i];};/*for*/ for i←1 to n do for j←i+1 to n do if (b[j+1]a[i])and(a[i]a[j]) /*若a[i]和a[j]不能不能压入同一个栈，则(i,j)和(j,i)进入邻接表*/ then { addedge(i,j);addedge(j,i)};/*then*/ for i←1 to n do /*所有未涂色的顶点涂颜色1，递归*/ if color[i]=0 then { color[i]←1;dfs(i)};/*then*/ 构造操作序列 last←1; /*目标序列初始化*/ for i←1 to n do /*模拟输出序列*/ { if color[i]=1