 LIS vs Kahn's algo||4ms Beats 98.50%
IntuitionUse a similar argument to LIS to solve the question.Using Graph Theory is possible, to find the longest chain!2nd approach uses toplogoical sort(Kahn's
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Use a similar argument to LIS to solve the question.

Using Graph Theory is possible, to find the longest chain! 

2nd approach uses toplogoical sort(Kahn's algorithm), a graphical BFS approach which is relatively slow but accepted. 
# Approach
<!-- Describe your approach to solving the problem. -->
1. Sort `nums`
2. Initialize state arrays with `len(n, 1), prev(n, -1)`
3. Use a nested loop to proceed the DP. If `nums[i] % nums[j] == 0 && len[i] < len[j] + 1` update len[i], prev[i]. If `len[i]>maxLen` update `maxLen, iMax`.
4. Use `prev` to construct `ans` and return it
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
 $$O(n^2)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n)$$
# C++ Code like LIS ||4ms Beats 98.50%
```cpp 
class Solution {
public:
    // similiar to LIS O(n^2) solution
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> len(n, 1), prev(n, -1);//state arrays

        int maxLen=0, iMax= -1;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j < n; j++) {
                if (nums[j]%nums[i]==0 && len[j]<len[i]+1) {
                    len[j]=len[i]+1;
                    prev[j]=i;
                }
            }
            if (len[i]>maxLen) {
                maxLen=len[i];
                iMax=i;
            }
        }
        
        vector<int> ans;
        for (int j=iMax; j!=-1; j=prev[j]) {
            ans.push_back(nums[j]);
        }
        return ans;
    }
};

auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
```
# Kahn's algorithm can solves many LC qestions
[207. Course Schedule](https://leetcode.com/problems/course-schedule/solutions/3756937/w-explanation-c-dfs-vs-bfs-kahn-s-algorithm/)
[210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)
[1203. Sort Items by Groups Respecting Dependencies
](https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/solutions/3933825/c-using-bfs-kahn-s-algorithm-vs-dfs-beats-97-67/)[LC 1203. Please turn on the English subtitles if necessary]
[https://youtu.be/vdar3a_ZdCI?si=B_rAuZaYP6JG4ybI](https://youtu.be/vdar3a_ZdCI?si=B_rAuZaYP6JG4ybI)
# C++ topological sort
```cpp
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        const int n = nums.size();
        vector<int> deg(n, 0), prev(n, -1);
        vector<vector<int>> adj(n);

        //Kahn's algo
        for (int i = 0; i < n; i++) {//Build adjacent list
            for (int j = i+1; j < n; j++) {
                if (nums[j] % nums[i] == 0) {
                    adj[i].push_back(j);
                    deg[j]++;//indegree
                }
            }
        }
        // BSF
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (deg[i]==0) q.push(i);
        }

        int iMax= 0;
        while (!q.empty()) {
            int x=q.front();
            q.pop();
            for (int y : adj[x]) {
                if (--deg[y] == 0) {
                    q.push(y);
                    prev[y]=x;//assign prev
                }
            }
            iMax=x;
        }
        vector<int> ans;
        for (int j=iMax; j!=-1; j=prev[j]) {
            ans.push_back(nums[j]);
        }
        return ans;
    }
};


```
['Dynamic Programming', 'Topological Sort', 'Sorting', 'C++']