thảo luận Leetcode mỗi ngày

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        ans = []
        m = len(land)
        n = len(land[0])
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        def dfs(row, col, id):
            if row < 0 or col < 0 or row >= m or col >= n or land[row][col] != 1:
                return
            land[row][col] = 2 # visited
            ans[id][0] = min(ans[id][0], row)
            ans[id][1] = min(ans[id][1], col)
            ans[id][2] = max(ans[id][2], row)
            ans[id][3] = max(ans[id][3], col)

            for i, j in dirs:
                dfs(row + i, col + j, id)

        for row in range(m):
            for col in range(n):
                if land[row][col] == 1:
                    ans.append([row, col, row, col])
                    dfs(row, col, len(ans) - 1)
        return ans

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m, n = len(land), len(land[0])
        ans = []
        def dfs(m, n, i, j):
            dx, dy = 0, 0
            while i + dy + 1 < m and land[i+dy+1][j] == 1:
                dy += 1
            while j + dx + 1 < n and land[i][j+dx+1] == 1:
                dx += 1
            return [i, j, i+dy, j+dx]
        for i in range(m):
            for j in range(n):
                if land[i][j] == 1:
                    la = dfs(m, n, i, j)
                    ans.append(la)
                    for ci in range(la[0], la[2]+1):
                        for cj in range(la[1], la[3]+1):
                            land[ci][cj] = 0
                    # print(land)
        return ans

def findFarmLand(land, meet, x, y):
    h, w = len(land), len(land[0])

    stack = []
    bot = (x, y)
    stack.append(bot)

    maxR, maxC = x, y

    while stack:
        r, c = stack.pop()

        if (r, c) not in meet:
            meet.add((r, c))
            if land[r][c] == 0:
                continue
            if r >= maxR and c >= maxC:
                maxR, maxC = r, c
            if r < h-1:
                stack.append((r+1, c))
            if c < w-1:
                stack.append((r, c+1))
            
    return maxR, maxC

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        meet = set()

        result = []

        for i in range(len(land)):
            for j in range(len(land[i])):
                if land[i][j] == 1 and (i, j) not in meet:
                    bot = findFarmLand(land, meet, i, j)
                    result.append([i, j, bot[0], bot[1]])

        return result

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        adj = {}
        for edge in edges:
            u, v = edge
            if u in adj:
                adj[u].append(v)
            else:
                adj[u] = [v]
            if v in adj:
                adj[v].append(u)
            else:
                adj[v] = [u]
        
        q = deque([source])
        result = False
        while q:
            vertex = q.popleft()
            if vertex == destination:
                result = True
                break
            if vertex in adj:
                for v in adj[vertex]:
                    q.append(v)
                del adj[vertex]
        
        return result

bool dfs(vector<vector<int>>& graph, int s, int d, unordered_set<int>& visited) {
    if (s == d) return true;
    for(auto v : graph[s]) {
        if (visited.count(v)) continue;
        visited.insert(v);
        if (dfs(graph, v, d, visited)) return true;
    }
    return false;
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<vector<int>> graph(n, vector<int>{});
    unordered_set<int> visited;
    for(auto e : edges) {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    return dfs(graph, source, destination, visited);
}

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph(n, vector<int>{});
        for(auto e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
       
        vector<int> visited(n, 0);
        queue<int> q;
        q.push(source);
        while(!q.empty()) {
            auto curr = q.front(); q.pop();
            if (curr == destination) return true;
            for(auto e : graph[curr]) {
                if (visited[e]) continue;
                visited[e] = 1;
                q.push(e);
            }
        }
        return false;
    }

var validPath = function(n, edges, source, destination) {
    const nb = [];
    edges.forEach(([a, b]) => {
        nb[a] ||= []; nb[a].push(b);
        nb[b] ||= []; nb[b].push(a);
    });
    const visited = [];
    const dfs = node => {
        if (visited[node]) {
            return false;
        }
        visited[node] = true;
        if (node === destination) {
            return true;
        }
        for (let next of nb[node]) {
            if (!visited[next]) {
                if (dfs(next)) {
                    return true;
                }
            }
        }
        return false;
    }
    return dfs(source);
};

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination: return True
        
        graph = defaultdict(list)
        for [s , e] in edges:
            graph[s].append(e)
            graph[e].append(s)

        vis = [False] * n
        par = [-1] * n
        def dfs(s):
            vis[s] = True
            for e in graph[s]:
                if vis[e] == False:
                    par[e] = s
                    dfs(e)

            return

        def validPath(start , end):
            while par[end] != -1:
                end = par[end]
                if end == start: return True
    
            return False

        dfs(source)

        return validPath(source ,destination)

var validPath = function(n, edges, source, destination) {
    if (source == destination) return true;
    const map = {};
    const visit = new Set();
    for (const [src, dest] of edges) {
        if (!map[src]) map[src] = [];
        if (!map[dest]) map[dest] = [];
        map[src].push(dest);
        map[dest].push(src);
    }

    var dfs = function (src, dest) {
        if (!map[src]) return false;
        if (src == dest) return true;
        visit.add(src);
        for (const v of map[src]) {
            if (!visit.has(v) && dfs(v, dest)) return true;
        }

        return false;
    }

    return dfs(source, destination);
};

class Solution {
public:
    int find_parent(vector<int> &p, int i) {
        int j = i;
        while (p[i] != -1) i = p[i];
        if (j != i) p[j] = i;
        return i;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> p(n,-1);
        for (auto &e : edges) {
            int p0 = find_parent(p, e[0]), p1 = find_parent(p, e[1]);
            if (p1 != p0) p[p1] = p0;
        }
        return find_parent(p,source) == find_parent(p,destination);
    }
};

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        Map<Integer, Queue<Integer>> ways = new HashMap<>();
        for(int[] edge : edges){
            Queue<Integer> way1 = ways.computeIfAbsent(edge[0], s -> new LinkedList<>());
            Queue<Integer> way2 = ways.computeIfAbsent(edge[1], s -> new LinkedList<>());
            way1.add(edge[1]);
            way2.add(edge[0]);
        }
        return dfs(ways, source, destination);
    }
    public boolean dfs(Map<Integer, Queue<Integer>> ways, int key, int destination){
        if(key == destination)
            return true;
        Queue<Integer> way = ways.get(key);
        while(!way.isEmpty()){
            int keyNext = way.poll();
            if(dfs(ways, keyNext, destination)){
                return true;
            }
        }
        return false;
    }
}

from queue import Queue
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        edgeHash = {}
        for edge in edges:
            if edge[0] in edgeHash:
                edgeHash[edge[0]].append(edge[1])
            else:
                edgeHash[edge[0]] = [edge[1]]
            if edge[1] in edgeHash:
                edgeHash[edge[1]].append(edge[0])
            else:
                edgeHash[edge[1]] = [edge[0]]
        queue = Queue()
        queue.put(source)
        visited = {}
        visited[source] = True
        while not queue.empty():
            cur = queue.get()
            if cur == destination:
                return True
            nexts = edgeHash.get(cur, [])
            for nextV in nexts:
                if nextV not in visited:
                    queue.put(nextV)
                    visited[nextV] = True
        return False

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> m(n);
        vector<int>v(n,0);
        v[source] = 1;
        for(auto &it: edges)
        {
            m[it[0]].push_back(it[1]);
            m[it[1]].push_back(it[0]);
        }
        queue<int> q;
        q.push(source);
        while(q.size())
        {
          auto item = q.front();
          q.pop();
          if(item == destination) return true;
          v[item] = 1;
          for(auto &it: m[item])
          {
              if(v[it] == 0)
              {
                  v[it] = 1;
                  q.push(it);
              }
          }
        }
        return false;
    }
};

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # Build graph
        graph = {}
        for edge in edges:
            if edge[0] not in graph:
                graph[edge[0]] = []
            if edge[1] not in graph:
                graph[edge[1]] = []
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])

        meet = set()
        stack = []
        stack.append(source)

        while stack:
            current = stack.pop()
           
            if current == destination:
                return True

            if current not in meet:
                meet.add(current)
               
                if current in graph:
                    for vertex in graph[current]:
                        stack.append(vertex)

        return False