Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 1466. Reorder Routes to Make All Paths Lead to the City Zero

---

參考資訊：
https://blog.csdn.net/fuxuemingzhu/article/details/106597991

題目：


解答：

#define COST 0x80000000

int travel(int **connections, int n, int *visit, int *len, int **cost, int cur)
{
    int r = 0;
    int i = 0;

    visit[cur] = 1;
    for (i = 0; i < len[cur]; i++) {
        int dst = cost[cur][i] & ~COST;

        if (visit[dst] == 0) {
            r += !!(cost[cur][i] & COST);
            r += travel(connections, n, visit, len, cost, dst);
        }
    }
    return r;
}

int minReorder(int n, int **connections, int connectionsSize, int *connectionsColSize)
{
    int i = 0;
    int **cost = NULL;
    int *len = calloc(n, sizeof(int));
    int *visit = calloc(n, sizeof(int));

    for (i = 0; i < connectionsSize; i++) {
        len[connections[i][0]] += 1;
        len[connections[i][1]] += 1;
    }

    cost = calloc(n, sizeof(int *));
    for (i = 0; i < n; i++) {
        cost[i] = calloc(len[i], sizeof(int));
    }

    memset(len, 0, sizeof(int) * n);
    for (i = 0; i < connectionsSize; i++) {
        int src = connections[i][0];
        int dst = connections[i][1];

        cost[src][len[src]++] = dst | COST;
        cost[dst][len[dst]++] = src;
    }

    return travel(connections, n, visit, len, cost, 0);
}