c++ | topological sort | graph
Did not see any graph based approach in the discuss section, so adding it here ^^\nNot the fastest approach but is intuitive.\nVisualize array of ratings as gra
Did not see any graph based approach in the discuss section, so adding it here ^^\nNot the fastest approach but is intuitive.\nVisualize array of ratings as graph. Edge(u --> v) is made when u < v.\nThen assign candies in topology sort order starting from 1 and increment after every level of bfs.\n```\nint candy(vector<int> &a)\n{\n    int n = a.size();\n    vector<int> adj[n];\n    vector<int> inDegree(n, 0);\n    for (int i = 0; i < n - 1; i++)\n    {\n        int u = a[i], v = a[i + 1];\n        if (v > u)\n            adj[i].push_back(i + 1), inDegree[i + 1]++;\n        else if (u > v)\n            adj[i + 1].push_back(i), inDegree[i]++;\n    }\n    queue<int> q;\n    for (int i = 0; i < n; i++)\n    {\n        if (inDegree[i] == 0)\n            q.push(i);\n    }\n    int ans = 0, curr = 1;\n    while (!q.empty())\n    {\n        int size = q.size();\n        while (size--)\n        {\n            int node = q.front();\n            q.pop();\n            ans += curr;\n            for (auto &x : adj[node])\n            {\n                inDegree[x]--;\n                if (inDegree[x] == 0)\n                    q.push(x);\n            }\n        }\n        curr++;\n    }\n    return ans;\n}\n```
['Breadth-First Search', 'Graph', 'Topological Sort', 'C', 'C++']