aboutsummaryrefslogtreecommitdiff
path: root/find_path_exist_graph.c
blob: d52dfa98b91faf02c6a9e81cf9f52aad0681f460 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 1971. Find if Path Exists in Graph
#include "leetcode.h"

/*
 * there is a bidirectional graph with 'n' vertices where each vertex is labeled
 * from 0 to 'n - 1' inclusive. the edges in the graph are rpresented as a 2d
 * integer array 'edges', where each 'edgies[i] = [ui, vi]', denotes a
 * bidirectional edge between vertex 'ui' and vertex 'vi'. every vertex pair is
 * connected by at most one edge, and no vertex has an edge to itself.
 */

bool validPath(int n, int **edges, int edgesSize, int *edgesColSize, int source,
               int destination) {
  if (source == destination)
    return 1;
  bool vis_map[n], stk_map[n];
  for (int i = 0; i < n; i++) {
    stk_map[i] = 0;
    vis_map[i] = 0;
  }
  int stk[n];
  uint pt = -1;
  stk[++pt] = source;
  stk_map[source] = 1;
  while (pt != -1) {
    while (vis_map[stk[pt]])
      pt--;
    vis_map[stk[pt]] = 1;
    int top = stk[pt--];
    stk_map[top] = 0;
    for (int i = 0; i < edgesSize; i++)
      for (int j = 0; j < *edgesColSize; j++)
        if (edges[i][j] == top) {
          int vertex = edges[i][*edgesColSize - j - 1];
          if (vertex == destination)
            return 1;
          if (!vis_map[vertex] && !stk_map[vertex]) {
            stk[++pt] = vertex;
            stk_map[vertex] = 1;
          }
          edges[i][j] = n;
          edges[i][*edgesColSize - j - 1] = n;
          break;
        }
  }
  return vis_map[destination];
}