[C] DFS, graph
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/*\n * 1466. Reorder Routes to Make All Paths Lead to the City Zero\n *\n * There are n cities numbered from 0 to n - 1 and n - 1 roads \n * such that there is only one way to travel between two different \n * cities (this network form a tree). Last year, The ministry of \n * transport decided to orient the roads in one direction because \n * they are too narrow.\n * \n * Roads are represented by connections where connections[i] = [ai, bi] \n * represents a road from city ai to city bi.\n * \n * This year, there will be a big event in the capital (city 0), and many \n * people want to travel to this city.\n * \n * Your task consists of reorienting some roads such that each city can \n * visit the city 0. Return the minimum number of edges changed.\n * \n * It\'s guaranteed that each city can reach city 0 after reorder.\n *\n * 2 <= n <= 5 * 10^4\n * connections.length == n - 1\n * connections[i].length == 2\n * 0 <= ai, bi <= n - 1\n * ai != bi\n *\n *\n */\n \ntypedef struct dst {\n    struct dst *next;\n    int id;\n} dst_t;\n \nint dfs(dst_t **orig_adj, dst_t **bidir_adj, int n, int curr, bool *visited)\n{\n    int cnt = 0;\n    bool same_dir = false;\n    \n    visited[curr] = true;\n    \n    /* Check if we can move to next node (away from node 0) */\n    for (dst_t *tmp1 = bidir_adj[curr]; tmp1; tmp1 = tmp1->next) {\n\n        if (visited[tmp1->id] == false) {\n        \n            same_dir = false;\n        \n            /* \n             * \n             * Check the original neighbor list, check if it is possible to \n             * move from the next city back to the current city.\n             * If not, we need to reverse the original road direction\n             */\n            for (dst_t *tmp2 = orig_adj[tmp1->id]; tmp2; tmp2 = tmp2->next) {\n                if (tmp2->id == curr) {\n                    same_dir = true;\n                    break;\n                }\n            }\n            \n            if (same_dir == false) {\n                cnt++;\n            }\n            \n            /* Move to next city, and contiune to check the roads between different cities */\n            cnt += dfs(orig_adj, bidir_adj, n, tmp1->id, visited);\n        }\n    \n    }\n\n    return cnt;\n}\n\n/*\n * Algorithm:\n *  We know that all the cities are connected together\n *  but some of roads have incorrect direct so this \n *  cause some cities can visit city 0\n *\n *  E.g:\n *      0  <-  1  ->  2  <- 3 -> 4\n *\n *  We can create a bidirectional map\n *      0  <-  1  ->  2  <- 3 -> 4\n *         ->     ->     ->   ->\n *\n *  Start to city 0, traverse to other cities and also compare the\n *  original road direction between these cities, its the direction is different\n *  we need to reverse the road direction\n *\n *      0  <-  1  ->  2  <- 3 -> 4\n *         ->     ->     ->   ->\n *          1             2             => Ans = 2;\n */\n \nint minReorder(int n, int** connections, int connectionsSize, int* connectionsColSize){\n\n    /*\n     * Input:\n     *  n, n cities\n     *  connections, roads between cities\n     *  connectionsSize, number of roads\n     *  connectionsColSize\n     */\n\n    int ans = 0;\n    bool *visited = (bool *)calloc(1, sizeof(bool) * n);\n    dst_t **orig_adj = (dst_t **)calloc(1, sizeof(dst_t *) * n);\n    dst_t **bidir_adj = (dst_t **)calloc(1, sizeof(dst_t *) * n);\n    dst_t *tmp, *del;\n    \n    /* Build origianl adjacent list and a bidirectional adjacent list */\n    for (int i = 0; i < connectionsSize; i++) {\n        /* orig_adj[from][to] */\n        tmp = (dst_t *)malloc(sizeof(dst_t));\n        tmp->id = connections[i][1];\n        tmp->next = orig_adj[connections[i][0]];\n        orig_adj[connections[i][0]] = tmp;\n        \n        /* Bidirection */\n        tmp = (dst_t *)malloc(sizeof(dst_t));\n        tmp->id = connections[i][1];\n        tmp->next = bidir_adj[connections[i][0]];\n        bidir_adj[connections[i][0]] = tmp;\n        \n        tmp = (dst_t *)malloc(sizeof(dst_t));\n        tmp->id = connections[i][0];\n        tmp->next = bidir_adj[connections[i][1]];\n        bidir_adj[connections[i][1]] = tmp;\n    }\n     \n    ans = dfs(orig_adj, bidir_adj, n, 0, visited);\n     \n    for (int i = 0; i < n; i++) {\n    \n        for (tmp = orig_adj[i]; tmp; ) {\n            del = tmp;\n            tmp = tmp->next;\n            free(del);\n        }\n        \n        for (tmp = bidir_adj[i]; tmp; ) {\n            del = tmp;\n            tmp = tmp->next;\n            free(del);\n        }\n\n    }\n\n    free(orig_adj);\n    free(bidir_adj);\n    free(visited);\n    \n    /*\n     * Output:\n     *  Return the minimum number of edges changed.\n     */\n     \n    return ans;\n}\n```
['Depth-First Search', 'Graph', 'C']