1. 勾稽关系
勾稽关系（Reconciliation Relationship）是一个财务术语，指的是在会计和审计中，不同会计报表或报表项目之间存在的逻辑对应关系。这种关系可以用来验证会计数据的准确性和完整性。勾稽关系通常体现在以下几个方面：
-
会计等式：资产 = 负债 + 所有者权益，这是会计的基本等式，也是最基础的勾稽关系。即 3 = 1+2 ， 4 = 5+ 2 , 7 = 1 + 6 .
这里的勾稽关系: 有
2.拓扑排序
简单来说就是一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。
举例子
开始时，图是这样的状态，发现A的入度为 0，所以删除A和A上所连的边，结果如下图：
这时发现B的入度为 0，C的入度为 0，所以删除B和B上所连的边、C和C上所连的边，结果如下图：
这时发现发现D的入度为 0，所以删除D和D上所连的边(如果有就删)，结果如下图：、
这时整个图被删除干净，所有能进行拓扑排序。
首先记录各个点的入度
然后将入度为 0 的点放入队列
将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1。
如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。
拓扑排序的实现(java)
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Main{static int N = 100010;static int[] h = new int[N]; //以第一个节点的编号为索引，存储所有单链表的头节点static int[] e = new int[N]; //以当前要操作的节点为索引，存储第二个节点的编号static int[] ne = new int[N]; //以当前操作的节点为索引，存储下一个节点static int[] d = new int[N]; //存储i号节点的入度static int[] top = new int[N];static Queue<Integer> q = new LinkedList<>();static int idx,n,cnt = 1; //cnt指的是top中有多少元素public static void main(String[] args){Scanner in = new Scanner(System.in);n = in.nextInt();int m = in.nextInt();for(int i = 0; i < N; i ++) h[i] = -1;for(int i = 0; i < m; i ++){int a = in.nextInt();int b = in.nextInt();add(a,b);d[b]++; //入度+1}if(topsort()){for(int i = 1; i <= n; i ++) System.out.print(top[i] + " ");}else System.out.print("-1");}private static void add(int a ,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;}private static boolean topsort(){for(int i = 1; i <= n; i ++) //因为是从1开始编号的，所以从1开始遍历{if(d[i] == 0) q.offer(i); //遍历每个节点，入度为0就入栈}while(q.size() != 0){int t = q.poll();top[cnt] = t;cnt++;for(int i =h[t]; i != -1; i = ne[i]) //遍历链表，删除1的所有出度{int j = e[i]; //j找到第一个节点指向的点bif(--d[j] == 0) q.offer(j); //删除边}}return cnt >= n; //注意这里一定是>=,因为cnt = 3以后会++等于4}
}3. 勾稽关系抽象成有向图
通过对勾稽关系的理解，其本质类似一种层级依赖关系，凡有层级依赖关系且是有向的依赖关系，因此可以抽象成一种树形结构，而勾稽关系的优先级恰好就是当前节点到最远的叶子节点的距离。因此可以在求拓扑排序的过程中求得。
其中 1= 2+3， 4 = 5+ 2 , 7 = 1 + 6
如下图 :
代码实现: 在求拓扑排序的过程中实现计算当前树节点的优先级
while(hh<=tt){int t = q[hh++];for(int i = h[t];i!=-1;i=ne[i]){int j = e[i];// 优先级获取的核心逻辑sort[j] =Math.max(sort[j],sort[t]+1) ;System.out.println("j-->sort[j] "+j+"-->"+sort[j]);System.out.println("t ----> j: "+t+"-->"+j);if(--d[j] == 0){q[++tt] = j;}}}最终的优先级关系:
2 -> 1
3 -> 1
1 -> 2
5 -> 1
6 -> 1
7 -> 3
5.完整代码:
import java.util.Arrays;/*** @author 16905*/
public class MyExpressionResolver {public final int N = (int)5e3;public int n,m,idx;public int[] ne= new int[N];public int[] e = new int[N];public int[] h = new int[N];public int[] q = new int[N];public int[] d = new int[N];public int[] sort = new int[N];int ans=N;// 链表头节点添加public void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a]= idx++;}/*** 拓扑排序* @return*/public int[] trop(){Arrays.fill(sort,0);
// 这里用到了 数组模拟队列int tt =-1,hh = 0;for(int i=1;i<=n;i++){if(d[i]==0){q[++tt] = i;}}while(hh<=tt){int t = q[hh++];for(int i = h[t];i!=-1;i=ne[i]){int j = e[i];// 优先级获取的核心逻辑sort[j] =Math.max(sort[j],sort[t]+1) ;System.out.println("j-->sort[j] "+j+"-->"+sort[j]);System.out.println("t ----> j: "+t+"-->"+j);if(--d[j] == 0){q[++tt] = j;}}}int[] sortEnd = new int[n+1];if(tt==n-1){System.out.print("得到拓扑序: ");for(int i=0;i<n;i++){System.out.printf("%d ",q[i]);}System.out.println();System.out.print("节点 : ");for(int i = 0,j=0; i<= n; i++){// 得到优先级System.out.printf("%d ",i);} System.out.println();System.out.print("优先级: ");for(int i = 0,j=0; i<= n; i++){// 得到优先级System.out.printf("%d ",sort[i]+1);sortEnd[j++] = sort[i];}}return sortEnd;}public static void main(String[] args) {MyExpressionResolver myExpressionResolver = new MyExpressionResolver();Arrays.fill(myExpressionResolver.h,-1);// 1->4 4++// 5->4// 2->1 1++// 3->1// 1->7 7++// 6->7String[] test = new String[]{"1=2+3","4=2+5","7=1+6"};for (String s : test) {String[] split = s.split("=");String replace = split[1].replace("+", "-").replace("*", "-").replace("/", "-");String[] rightValue = replace.split("-");int left = Integer.parseInt(split[0]);for (String right : rightValue) {myExpressionResolver.d[left] ++;myExpressionResolver.add(Integer.parseInt(right),left);}}// 7// / \// 4 1 6// / \ / \// 5 2 3myExpressionResolver.n = 7;int[] sortAns = myExpressionResolver.trop();System.out.println();System.out.print("得到最终的节点优先级:");for (int sortAn : sortAns) {System.out.print( " "+sortAn );}System.out.println();}}
程序运行结果:(观察可得与实际结果一致)
