1.常见数据结构的作用：

处理算法时如何使用正确高效的数据结构解决问题非常关键。

数组/链表：处理的是线性关系。数据一个接一个地排列。
树：处理的是分层级、一对多的关系。有明确的父节点和子节点，且通常没有环路。
图： 处理的是任意、复杂的关系。实体间的关系可以是多对多的，可以形成环路，可以没有固定的方向。

2.图

尤其解决多对多的关系时，可以使用图来解决：
1.无向图
社交网络 (无向图)
顶点：人。
边：好友关系。
解决的问题：推荐你可能认识的人、寻找最短的熟人关系链、分析信息传播路径。
2.有向图
互联网 (有向图)
顶点：网页。
边：超链接（从A网页指向B网页）。
解决的问题：网页排名(PageRank)、网络爬虫的抓取路径。
3.带权图
交通网络 (带权图)
顶点：城市或十字路口。
边：公路/航线。
边的权重：距离、时间或成本。

解决的问题：GPS导航计算最短路径、物流公司规划最优运输路线。
任务依赖关系 (有向无环图DAG)
4.任务图
顶点：任务。
边：依赖关系（任务A必须在任务B之前完成）。
解决的问题：制定项目计划、确定任务执行顺序。

5.简单题目：
小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：
1.小镇法官不会信任任何人。
2.每个人（除了小镇法官）都信任这位小镇法官。
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

问题分析：使用有向图解决，其中每个节点代表一个人，边代表信任关系。法官的入度应为n-1（被其他所有人信任），出度应为0（不信任任何人）。

算法选择：使用两个数组indegree和outdegree来记录每个节点的入度和出度。遍历信任数组，更新这两个数组。然后检查是否存在一个节点满足入度为n-1且出度为0。

 public int findJudge(int n, int[][] trust) {
            // 创建入度和出度数组，索引从1开始
            int[] indegree = new int[n + 1];
            int[] outdegree = new int[n + 1];

            // 遍历信任关系，更新入度和出度
            for (int[] relation : trust) {
                int a = relation[0]; // 信任者
                int b = relation[1]; // 被信任者
                outdegree[a]++;
                indegree[b]++;
            }

            // 检查是否存在法官
            for (int i = 1; i <= n; i++) {
                if (indegree[i] == n - 1 && outdegree[i] == 0) {
                    return i;
                }
            }
            return -1;
        }

    public static void main(String[] args) {
        GraphDemo solution = new GraphDemo();
        // 编号为1的信任编号为2的
        int n1 = 2;
        int[][] trust1 = {{1, 2}};
        System.out.println(solution.findJudge(n1, trust1)); // 输出: 2
    }

6.难度题目：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中省份的数量。
问题分析：实际是统计连通分量的个数
算法分析：使用并查集（一种树形结构，用于不相交集合的合并与查询）

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        
        // 遍历矩阵，合并相连的城市
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        
        return uf.getCount();
    }
    
    // 并查集类
    class UnionFind {
        private int[] parent;
        private int[] rank;  // 用于按秩合并，这里的秩指的是树的高度
        private int count;   // 连通分量数量
        
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            
            // 初始化，每个节点都是自己的父节点
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }
        
        // 查找根节点（路径压缩）
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);  // 路径压缩
            }
            return parent[x];
        }
        
        // 合并两个节点
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX != rootY) {
                // 按秩合并
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                count--;
            }
        }
        
        public int getCount() {
            return count;
        }
    }
}