Premium Algo 100 - Graph

Premium Algo 주제인 Graph 다.

---

Find the Celebrity
link : https://leetcode.com/problems/find-the-celebrity/description/?envType=study-plan-v2&envId=premium-algo-100

/* The knows API is defined for you.
      bool knows(int a, int b); */

/*
Time Complexity : O(n^2) 
Space Complexity : O(n) 
*/
class Solution {
public:
    int findCelebrity(int n) {
        vector<pair<int,int>> celebList(n); 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j) continue; 
                if(knows(i,j)){
                    celebList[i].first++; 
                    celebList[j].second++; 
                }
            }
        }

        for(int i = 0; i < celebList.size(); i++){
            if(celebList[i].first == 0 && celebList[i].second == n-1){
                return i; 
            }
        }

        return -1; 
    }
};

/* The knows API is defined for you.
      bool knows(int a, int b); */

/*
Time Complexity : O(n) 
Space Complexity : O(1) 
*/
class Solution {
public:
    int findCelebrity(int n) {
        int candidate = 0; 
        for(int i = 0; i < n; i++){
            if(candidate == i) continue; 
            if(knows(candidate,i)){
                candidate = i; 
            } 
        }

        for(int i = 0; i < n; i++){
            if(i == candidate) continue; 
            if(!knows(i,candidate) || knows(candidate,i)){
                return -1; 
            }
        }

        return candidate; 
    }
};

Kill Process
link : https://leetcode.com/problems/kill-process/description/?envType=study-plan-v2&envId=premium-algo-100

/*
Time Complexity : O(N)
Space Comlexity : O(N)
*/

class Solution {
public:
    vector<int> answer; 
    void dfs(vector<vector<int>>& adj, int kill){
        answer.push_back(kill); 
        for(int next : adj[kill]){
            dfs(adj,next); 
        }
    }
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        int node_num = *max_element(pid.begin(), pid.end()); 
        vector<vector<int>> adj(node_num + 1); 
        for(int i = 0; i < pid.size(); i++){
            if(ppid[i] == 0) continue; //root 
            adj[ppid[i]].push_back(pid[i]); 
        }

        dfs(adj,kill);

        return answer; 
    }
};

Web Crawler
link : https://leetcode.com/problems/web-crawler/description/?envType=study-plan-v2&envId=premium-algo-100

/**
 * // This is the HtmlParser's API interface.
 * // You should not implement it, or speculate about its implementation
 * class HtmlParser {
 *   public:
 *     vector<string> getUrls(string url);
 * };
 */
 

class Solution {
public:
    vector<string> answer; 
    map<string,bool> hashMap; 
    string getHostName(string &s){
        return s.substr(0,s.find('/',7));
    }

    void dfs(string& startUrl, HtmlParser htmlParser, string& hostName){
        if(getHostName(startUrl) == hostName) answer.push_back(startUrl); 
        hashMap[startUrl] = true; 
        for(string& nextUrl : htmlParser.getUrls(startUrl)){
            string nextHost = getHostName(nextUrl); 
            if(hashMap[nextUrl] == false && nextHost == hostName){
                dfs(nextUrl,htmlParser,hostName); 
            }
        }
    }
    vector<string> crawl(string startUrl, HtmlParser htmlParser) {
        string host = getHostName(startUrl);
        dfs(startUrl, htmlParser, host); 

        return answer; 
    }
};

Number of Connected Components in an Undirected Graph
link : https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/?envType=study-plan-v2&envId=premium-algo-100

/*

Time Complexity : O(V + E) 
Space Complexity : O(V + E);

*/

class Solution {
public:
    bool visited[2001]; 
    void dfs(vector<vector<int>>& adj, int node){
        visited[node] = true;
        for(int next : adj[node]){
            if(!visited[next]){
                dfs(adj,next); 
            }
        }
    }
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n); 
        for(vector<int>& v : edges){
            int from = v[0], to = v[1]; 
            adj[from].push_back(to); 
            adj[to].push_back(from); 
        }

        int answer = 0; 
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                answer++;
                dfs(adj,i); 
            }
        }
        return answer; 
    }
};

All Paths from Source Lead to Destination
link : https://leetcode.com/problems/all-paths-from-source-lead-to-destination/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    /*
    Time complexity : O(E + V) 
    Space complexity : O(E + V) 
    */ 
    int visited[10001]; 
    bool dfs(vector<vector<int>>& adj, int source, int destination){
        if(visited[source] == 1) return false; 
        if(visited[source] == 2) return true; 
        visited[source] = 1; 
        for(int next : adj[source]){
            if(!dfs(adj,next,destination)) return false; 
        }
        visited[source] = 2; 
        if(adj[source].size() == 0 && source != destination) return false; 
        return true; 
    }
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> adj(n); 
        for(vector<int>& v : edges){
            int from = v[0], to = v[1]; 
            adj[from].push_back(to); 
        }

        return dfs(adj,source,destination); 
    }
};

Number of Distinct Islands
link : https://leetcode.com/problems/number-of-distinct-islands/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
/*
time complexity : O(M * N)
space complexity : O(M * N) 
*/ 
    void dfs(vector<vector<int>>& grid, string& tmp, int i, int j){
        if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1){
            return; 
        }

        grid[i][j] = 0; 
        dfs(grid,tmp+='d',i+1,j); 
        dfs(grid,tmp+='u',i-1,j);
        dfs(grid,tmp+='l',i,j-1);
        dfs(grid,tmp+='r',i,j+1); 
    }
    int numDistinctIslands(vector<vector<int>>& grid) {
        set<string> stringSet; 
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 1){
                    string tmp = ""; 
                    dfs(grid,tmp,i,j); 
                    stringSet.insert(tmp); 
                }
            }
        }
        return stringSet.size(); 
    }
};

Parallel Courses :
link : https://leetcode.com/problems/parallel-courses/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
/*
Time complexity : O(E + V)
Space Complexity : O(E + V); 
*/
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        vector<vector<int>> adj(n+1); 
        vector<int> indegree(n+1); 
        for(vector<int>& v : relations){
            int from = v[0], to = v[1]; 
            adj[from].push_back(to); 
            indegree[to]++; 
        }

        queue<int> q; 
        for(int i = 1; i <= n; i++){
            if(indegree[i] == 0){
                q.push(i); 
            }
        }

        int time = 0; 
        int nodes = 0; 
        while(!q.empty()){
            int size = q.size();
            time++; 
            for(int i = 0; i < size; i++){
                int node = q.front();
                q.pop(); 
                nodes++; 
                for(int next : adj[node]){
                    indegree[next]--; 
                    if(indegree[next] == 0){
                        q.push(next); 
                    }
                }
            } 
        }
        //cout << nodes << ' ' << time; 
        return nodes == n ? time : -1; 
    }
};

---

복습 필요한 문제

1. Kill Process : 지금 푸는 방식은 너무 인접 리스트를 크게 한다. HashMap 방식으로 풀면은 더 깔끔할거같다.