[1971] Find if Path Exists in Graph

偷吃步 a.k.a 先偷看解答的寫法！原來有一種東西叫做union find Orz

leetcode 不管寫幾題，總是有新的東西呢T.T

好像可以不用size ! 但我猜那是比較正統的寫法(吧)

如果直接下去寫，應該會用DFS寫（thinking圖）

(烙一個DFS好像很會，但又沒真的下去寫XD）

演算法就是：程式碼好像很簡潔，但乍看之下 "完全看不懂" 的一種東西。

可讀性爛透了XD

int union_find(int *_union ,int val)

{

if (_union[val]==val)

return val;

return union_find(_union, _union[val]);

}

void union_set(int *_union, int v1, int v2)

{

int root1 = union_find(_union, v1);

int root2 = union_find(_union, v2);

if (root1 > root2)

_union[root1] = _union[root2];

else if (root1 < root2)

_union[root2] = _union[root1];

return; //root1 == root2 do nothing

}

bool validPath(int n, int** edges, int edgesSize, int* edgesColSize,

int source, int destination) {

int *_union = calloc(n, sizeof(int));

for (int i=0; i<n;i++) //init union

_union[i]= i;

//set union

for (int i=0; i<edgesSize; i++)

union_set(_union, edges[i][0], edges[i][1]);

return (union_find(_union,source) == union_find(_union,destination));

}