leetcode図

997.町を見つけた裁判官
裁判官は出度0、入度n-1の結点であり、唯一の

class Solution {
public:
    int findJudge(int N, vector<vector<int>>& trust) {
        //       0，   n-1   ，      
        vector<int> inDegree(N+1, 0);
        vector<int> outDegree(N+1, 0);

        for(int i = 0; i < trust.size(); i++){
            int start = trust[i][0];
            int end = trust[i][1];

            inDegree[end]++;
            outDegree[start]++;
        }

        for(int i = 1; i <= N; i++){ 
            if(outDegree[i] == 0 && inDegree[i] == N-1){
                return i;
            }
        }
        return -1;
    }
};

1042.不隣接植花
隣接テーブルを初期化し、デフォルトで0に染色し、隣接テーブルの色を順次削除すればよい

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {

        //      
        vector<int> G[N]; 
        for(int i = 0; i < paths.size(); i++){
            G[paths[i][0]-1].push_back(paths[i][1]-1);
            G[paths[i][1]-1].push_back(paths[i][0]-1);
        }
        vector<int> ans(N, 0); //          ， 0

        for(int i = 0; i < N; i++){
            set<int> color{1, 2, 3, 4}; //          ，            color{1,2,3,4}        ；
            for(int j = 0; j < G[i].size();j++){ //      ，        
                color.erase(ans[G[i][j]]); //         
            }
            ans[i] = *(color.begin()); //   ，            ，                    ，    ，                ；
        }
        return ans;
    }
};

133.クローン図
DFS

class Solution {
public:
    Node* cloneGraph(Node* node) {
        // DFS
        if(node == NULL){
            return NULL;
        }
        unordered_map<Node*, Node*> visited;
        Node* node_clone = dfs(node, visited);
        return node_clone;
    }

    Node* dfs(Node* node, unordered_map<Node*, Node*>& visited){
        if(visited.find(node) != visited.end()){
            //     ，      
            return visited[node];
        }
        Node* node_clone = new Node(node->val); //       
        visited[node] = node_clone; //           

        for(int i = 0; i < node->neighbors.size(); i++){
            //     
            Node* node_neighbour_clone = dfs(node->neighbors[i], visited); //          
            node_clone->neighbors.push_back(node_neighbour_clone); //         
        }
        return node_clone;
    }
};

BFS

class Solution {
public:
    Node* cloneGraph(Node* node) {
        // BFS
        if(node == NULL){
            return NULL;
        }
        unordered_map<Node*, Node*> mmap; //         

        Node* head = new Node(node->val);
        mmap[node] = head;

        queue<Node*> q;
        q.push(node);

        while(!q.empty()){
            Node* temp = q.front(); //       
            q.pop(); //    

            for(auto neighbor_node : temp->neighbors){ //       
                if(mmap.find(neighbor_node) == mmap.end()){
                    // mmap    ，      
                    mmap[neighbor_node] = new Node(neighbor_node->val); //       mmap 
                    q.push(neighbor_node);  //     
                    mmap[temp]->neighbors.push_back(mmap[neighbor_node]);  //   temp      
            }
        }
        return head;
    }

};

面接問題04.01.ノード間パス
BFS

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        // BFS
        vector<bool> visited(n);
        visited[start] = true; //          

        vector<vector<int>> map(n);

        //       
        for(int i = 0; i < graph.size(); i++){
            map[graph[i][0]].push_back(graph[i][1]);
        }  

        //   
        queue<int> q;
        q.push(start);

        while(!q.empty()){
            int temp = q.front();
            q.pop();

            if(temp == target){
                //      
                return true;
            }

            for(int i = 0; i < map[temp].size(); i++){
                if(!visited[map[temp][i]]){
                    //           
                    q.push(map[temp][i]);
                    visited[map[temp][i]] = true; //      
                }
            }
        }
        return false;
    }
};

DFS

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        // DFS
        vector<int> visited(n, false);
        vector<vector<int>> map(n);

        //       
        for(int i = 0; i < graph.size(); i++){
            map[graph[i][0]].push_back(graph[i][1]);
        }

        bool found = false;
        dfs(map, start, target, found, visited);
        return found;
    }

    void dfs(vector<vector<int>>& map, int start, int target, bool& found, vector<int>& visited){
        if(found){
            return;
        }
        if(start == target){
            found = true;
        }
        for(int i = 0; i < map[start].size(); i++){
            if(!visited[map[start][i]]){
                //      
                visited[map[start][i]] = true;
                dfs(map, map[start][i], target, found, visited);
                visited[map[start][i]] = false;
            }
        }
    }
};

785.判断二分図
染色法、DFS

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int size = graph.size();
        if(size == 0){
            return false;
        }
        //     ，         ：0       ， 1       2      。
        vector<int> color(size, 0);
        for(int i = 0; i < size; i++){
            if(!dfs(graph, color, i, 0)){
                return false;
            }
        }
        return true;
    }
//             u，        ，             v，    v           u  ，        。
//       v     ，        u       ，         v     ...      。
    bool dfs(vector<vector<int>>& graph, vector<int>& color, int i, int lastColor){
        if(color[i] != 0){
            //       
            return color[i] != lastColor; //           ,       u        
        }
        //      ，    lastColor 1   2
        color[i] = ( (lastColor == 1) ? 2 : 1);

        for(int j = 0; j < graph[i].size(); j++){
            if(!dfs(graph, color, graph[i][j], color[i])){
                return false;
            }
        }
        return true;
    }

};

BFS

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int size = graph.size();
        if(size == 0){
            return false;
        }
        //     ，         ：0       ， 1       2      。
        vector<int> color(size, 0);
        for(int i = 0; i < size; i++){
            if(color[i] == 0){
                if(!bfs(graph, color, i)){
                    return false;
                }
            }
        }
        return true;
    }

    bool bfs(vector<vector<int>>& graph, vector<int>& color, int i){
       queue<int> q;
       q.push(i);
       int lastColor = 0;

       while(!q.empty()){
            int temp = q.front();
            q.pop();
            lastColor = color[temp];
            
            for(int j = 0; j < graph[temp].size(); j++){//     
                //          queue
                //       graph      （        j。。。）
                int v = graph[temp][j];
                if(color[v] == 0){
                    q.push(v);
                    //   ，        color   
                    color[v] = (lastColor == 1) ? 2 : 1; 
                }else if(color[v] == lastColor){
                    //       ，           
                    return false;
                }
            }
        }
        return true;
    }

};

399.除算評価
2パーセント、図に2点の間に経路があるかどうかを求めて、DFS

class Solution {
public:
    //    
    unordered_map<string, vector<pair<string, double>>> m; 
    //   
    vector<double> ans;

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {

        //       
        for(int i = 0; i < equations.size(); i++){
            m[equations[i][0]].push_back(pair<string, double>(equations[i][1], values[i]));
            m[equations[i][1]].push_back(pair<string, double>(equations[i][0], 1/values[i]));
        }
        //   
        for(auto x: queries){
            if(x[0] == x[1]){
                //         
                if(m.find(x[0]) != m.end()){
                    //      
                    ans.push_back(1.0);
                }else{
                    //    equation      ，       
                    ans.push_back(-1.0);
                }
            }else{
                //      
                unordered_set<string> visited; //         
                visited.insert(x[0]);
                // dfs            
                if(dfs(x[0], x[1], 1.0, visited)){
                    //     
                    continue;
                }else{
                    //      
                    ans.push_back(-1.0);
                }
            }
        }
        return ans;
    }

    bool dfs(string start, string end, double curAns, unordered_set<string>& visited){
        if(start == end){
            //    
            ans.push_back(curAns);
            return true;
        }
        //     end   
        visited.insert(start);
        for(auto x: m[start]){
            if(visited.find(x.first) != visited.end()){
                //       x  
                continue;
            }else{
                if(dfs(x.first, end, curAns * x.second, visited)){
                    //      
                    return true;
                }
            }
        }
        return false;
    }
};

BFS

class Solution {
public:
    //    
    unordered_map<string, vector<pair<string, double>>> m; 
    //   
    vector<double> ans;

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {

        //       
        for(int i = 0; i < equations.size(); i++){
            m[equations[i][0]].push_back(pair<string, double>(equations[i][1], values[i]));
            m[equations[i][1]].push_back(pair<string, double>(equations[i][0], 1/values[i]));
        }
        //   
        for(auto x: queries){
            if(x[0] == x[1]){
                //         
                if(m.find(x[0]) != m.end()){
                    //      
                    ans.push_back(1.0);
                }else{
                    //    equation      ，       
                    ans.push_back(-1.0);
                }
            }else{
                // dfs            
                if(bfs(x[0], x[1])){
                    //     
                    continue;
                }else{
                    //      
                    ans.push_back(-1.0);
                }
            }
        }
        return ans;
    }

    bool bfs(string start, string end){
        // bfs
        unordered_set<string> visited;

        queue<pair<string, double>> q;
        q.push(pair<string, double>(start, 1.0));

        visited.insert(start);

        while(!q.empty()){
            auto temp = q.front();
            q.pop();

            if(temp.first == end){
                //        
                ans.push_back(temp.second);
                return true;
            }

            for(auto x: m[temp.first]){
                if(visited.find(x.first) != visited.end()){
                    //      visited  ，           ，  
                    continue;
                }else{
                    //       
                    q.push(pair<string, double>(x.first, x.second * temp.second));
                    visited.insert(x.first);
                }
            }
        }
        return false;
    }
};

802.最終的なセキュリティ状態を見つける
トポロジのソート

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();

        vector<int> outDegree(n, 0); // out degree
        vector<vector<int>> revGraph(n, vector<int>{}); // reverse graph
        vector<int> ans;

        // init outDegree and revGraph
        for(int i = 0; i < n; i++){
            outDegree[i] = graph[i].size();
            for(auto end: graph[i]){
                revGraph[end].push_back(i); // reverse graph
            }
        }

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

        // 
        while(!q.empty()){

            auto temp = q.front();
            q.pop();
            //      0   ，        
            ans.push_back(temp);
            
            //         0        ，       
            for(auto start: revGraph[temp]){
                outDegree[start]--;
                if(outDegree[start] == 0){
                    q.push(start);
                }
            }
        }

        sort(ans.begin(), ans.end());
        return ans;
    }
};

1203.プロジェクト管理
階層トポロジソートグループ間グループ内

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        //                    。
        //           ，             。
        //               ，                。
        // n   ，m   
        //     
        int maxGroup = m;
        for(int i = 0; i < group.size(); i++){
            if(group[i] == -1){
                //           
                group[i]= maxGroup++;
            }
        }
        vector<set<int>> groupItem(maxGroup); //         
        vector<int> groupIndegree(maxGroup, 0); //     
        vector<set<int>> groupGraph(maxGroup); //   - 
        
        vector<int> itemIndegree(n, 0); //           
        vector<set<int>> itemGraph(n); //          
        //    groupItem，            
        for(int i = 0; i < group.size(); i++){
            groupItem[group[i]].insert(i);
        }
        //         
        for(int i = 0; i < beforeItems.size(); i++){
            for(auto bi: beforeItems[i]){
                if(group[i] == group[bi]){
                    //           
                    itemIndegree[i]++; 
                    itemGraph[bi].insert(i); // bi->i
                }else{
                    //                          
                    if(groupGraph[group[bi]].count(group[i]) == 0){
                        // bi->i bi    
                        groupIndegree[group[i]]++; // i      +1
                        groupGraph[group[bi]].insert(group[i]); //    
                    }
                }
            }
        }
        //        
        vector<int> ans;
        queue<int> q;
        //    0     
        for(int i = 0; i < maxGroup; i++){
            if(groupIndegree[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){
            auto temp = q.front();
            q.pop();
            ans.push_back(temp);
            for(auto& i: groupGraph[temp]){
                groupIndegree[i]--;
                if(groupIndegree[i] == 0){
                    q.push(i);
                }
            }
        }

        if(ans.size() != maxGroup){
            return vector<int>();
        }

        //      
        vector<int> res;
        for(int i = 0; i < ans.size(); i++){
            for(auto& gi: groupItem[ans[i]]){
                if(itemIndegree[gi] == 0){
                    q.push(gi);
                }
            }
            int count = 0;
            while(!q.empty()){
                auto temp = q.front();
                q.pop();
                count++;
                res.push_back(temp);
                for(auto& ig: itemGraph[temp]){
                    itemIndegree[ig]--;
                    if(itemIndegree[ig] == 0){
                        q.push(ig);
                    }
                }
            }

            if(count != groupItem[ans[i]].size()){
                return vector<int>();
            }
        }
        return res;
    }
};

684.冗長接続
コレクションを調べる

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> rp(1001);
        int size = edges.size();

        //    
        for(int i = 0; i < size; i++){
            rp[i] = i;
        }

        for(int i = 0; i < size; i++){
            int set1 = find(edges[i][0], rp);
            int set2 = find(edges[i][1], rp);

            if(set1 == set2){
                //              ，    
                return edges[i];
            }else{
                //       ，    
                rp[set1] = set2;
            }
        }
        return {0, 0};
    }
    //            ，           ，              
    int find(int n, vector<int>& rp){
        int temp = n;
        while(rp[temp] != temp){
            temp = rp[temp];
        }
        return temp;
    }
};