May brush question 27 - figure

Today's brush topic content ： chart

Preface

• An algorithm opens the way to brush the questions of waste materials , Update the problem solution content of the problem brush every day
• Focus on personal understanding , Look at the difficulty and update the number of questions
• The title comes from Li Kou
• Try to work out at least one question every day
• Language java、python、c\c++

---

One 、 Today's topic

I only did two questions , I didn't have much time to write solutions yesterday , Make up today , The next two questions will be brushed later when you are not so busy

1. 1791. Find the central node of the star graph
2. 797. All possible paths
3. 851. Noise and wealth
4. 959. Area by slash

Two 、 Their thinking

1. 1791. Find the central node of the star graph

1. edges[i] Both are composed of two nodes , It is known that the central node will be connected to all other nodes
2. Select any point from a set of nodes , Compare with two points in another node set
3. If it appears in another node set, it means that this point is the central node
4. Otherwise, it is another node

class Solution {
    
    public int findCenter(int[][] edges) {
    
        int e = edges[0][0];
        if (e == edges[1][0] || e == edges[1][1]){
    
            return e;
        }
        return edges[0][1];
    }
}
/* *  Judge according to the edge , If it is the center point , It must appear in both sets  */

---

2. 797. All possible paths

Depth first search again , Let's use recursion first , Next time use a loop to solve

1. To find all the paths , That is, violent enumeration
2. graph[i] Indication point i All point sets that can be reached
3. Define a stack stack, Initial deposit 0 This node
4. The delivery process puts all points on the stack , If the end point is the last node , Then put stack Add the contents of to the list
5. In the process of returning stack Out of the stack

class Solution {
    
    List<Integer> stack;
    List<List<Integer>> ret;
    
    public void dfs(int n, int[][]graph, int now){
    
        if (now == n - 1){
    
            ret.add(new ArrayList<>(stack));  //  It can't be passed in directly stack, Only one object can be copied deeply 
            return;
        }
        for(int i = 0; i < graph[now].length; i++){
    
            stack.add(graph[now][i]);
            dfs(n, graph, graph[now][i]);
            stack.remove(stack.size() - 1);
        }
    }
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    
        int n = graph.length;  //  Get the number of all points 
        stack = new ArrayList<>();
        ret = new ArrayList<>();
        stack.add(0);
        dfs(n, graph, 0);
        return ret;
    }
}
/* * dfs( Number to find ,  Adjacency matrix ,  The current number ) */

---

3. 851. Noise and wealth

---

4. 959. Area by slash