GeekPractice_DFS - meruneru/tech_memo GitHub Wiki

GeekPractice DFS

解いた問題の備忘録

2辺連結グラフ、強連結グラフ、非巡回グラフ、トポロジカル順序を調べる

DFSは探索中のノードしか持ってないので、メモリ的にはいいけど、最短経路を求めるのには向いてない。(全部探索完了しないと最短か分からないため)

DFS of Graph

問題

graph TD;

0-->1;
0-->2;
0-->3;
2-->4;
Loading

OUTPUT: 0 1 2 4 3

何故か問題のC言語設定とC++設定で関数名が違う不具合があり、躓いた。 また、変数Vが現在着目しているノードだと思ったけど違ったし、dfsOfGraph()の戻り値の解釈も間違っていた。あと、たぶん問題文の図は間違っている。

変数Vは、ノード数なことに注意。また、訪れた順にvectorにpush_backしたモノがdfsOfGraph()の計算結果であることにも注意。(Mainでそれを出力している)

vectorの配列という見慣れない型を使う必要があった。 adj[4]の型がvector<int>と理解すれば、単なる2重ベクタか。 for(int j: adj[current])で各値にアクセスできるのも納得。

class Solution {
  public:
    
    void dfsUtil(int current, vector<int> adj[], bool visited[], vector<int>& res){
        if(visited[current])return;
        visited[current]=true;
        
        res.push_back(current);
        for(int j: adj[current]){
            if(!visited[j]){
                dfsUtil(j, adj, visited, res);
            }
        }
    }
    
    // Function to return a list containing the DFS traversal of the graph.
    vector<int> dfsOfGraph(int V, vector<int> adj[]) {
        bool visited[V];
        memset(visited, false, sizeof(visited));
        
        vector<int> res;
        for(int i=0; i<V; i++){
            if(visited[i])continue;
            
            dfsUtil(i, adj, visited, res);
        }
        return res;
    }
};

// { Driver Code Starts.
int main() {
    int tc;
    cin >> tc;
    while (tc--) {
        int V, E;
        cin >> V >> E;

        vector<int> adj[V];

        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // string s1;
        // cin>>s1;
        Solution obj;
        vector<int> ans = obj.dfsOfGraph(V, adj);
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
    }

Unit Area of largest region of 1's

問題

Gridの中の1の集団の個数を数える問題。 ８方位に対してDFSを行う。

一度数えた場所はゼロにする。

また、集団は分離している可能性もあるので、 それぞれの集団の最大値を求める必要がある。

DFSを１回すると１集団すべてをゼロにすることができるので、 何回かDFSを呼び出してあげる構造にする必要がある。

２重vectorでX, Yのsize()を求めるのに戸惑った。 vector<vector<int>> gridのX/Yそれぞれのsizeはgrid.size(), grid[0].size()で求まる。

    void dfs(int x, int y, vector<vector<int>>& grid, int& cnt){
        if(x<0 || y<0 || x>=grid.size() || y>=grid[x].size()){
            return;
        }
        
        if(grid[x][y]==0){
            return;
        }
        
        cnt++;
        grid[x][y]=0;
        
        int dict[8][2]={{1,1}, {1,-1}, {-1,1}, {-1,-1},
                        {0,1}, {0,-1}, {1, 0}, {-1,0}};
        
        for(int i=0; i<8; i++){
            dfs(x+dict[i][0], y+dict[i][1], grid, cnt);
        }
    }
    //Function to find unit area of the largest region of 1s.
    int findMaxArea(vector<vector<int>>& grid) {
        int res=0;
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[i].size(); j++){
                if(grid[i][j]==1){
                    int cnt = 0;
                    dfs(i, j, grid, cnt);
                    res=std::max(res, cnt);
                }
            }
        }
        return res;
    }

Find ehether path exist

Find whether path exist

#Unit Area of largest region of 1'sとよく似た問題。 スタートからゴールまでたどり着けるか？という問題。

    void dfs(int x, int y,vector<vector<int>>& grid, bool& ret){
        if(x<0 || y<0|| x>=grid.size() || y>=grid[x].size()){
            return;
        }
        if(grid[x][y]==0){ // Wall
            return;
        }else if(grid[x][y]==2){
            ret = true;
            return;
        }else{
            grid[x][y]=0;
        }
        
        dfs(x+1, y, grid, ret);
        dfs(x-1, y, grid, ret);
        dfs(x, y+1, grid, ret);
        dfs(x, y-1, grid, ret);
    }
    //Function to find whether a path exists from the source to destination.
    bool is_Possible(vector<vector<int>>& grid) 
    {
        bool ret=false;
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[i].size(); j++){
                if(grid[i][j]==1){
                    dfs(i, j, grid, ret); 
                }
            }
        }
        return ret;
    }

Detect cycle in an undirected graph

問題

graph TD;

0---1;
1---2;
2---3;
3---4;
4---1;
Loading

グラフにループがあるか判定する問題。

  1. 初めて訪れるノードの場合、DFSでどんどん深堀していく
  2. 1度訪れたことがあるノートの場合、ループか判定する
    1. 孤立ノードの場合は、ループと判定したくない
    2. 現在のノードに遷移する直前に居たルート(parent)と異なる場合だけをループとする

dfs()実装の注意点としては、深堀する場合は深堀する事だけを行い、ループ判定処理を行わないようにする。 無向グラフなため、adj[]のforループでは来たルートも格納されていて、ループ判定処理を行う(つまりは、else if のelseが無い場合)と、ループtrueとなってしまう。

  bool dfs(int num, vector<int> adj[], vector<bool>& visit, int parent){
      visit[num]=true;
      for(int i: adj[num]){
          if(visit[i]==false){
            if(dfs(i, adj, visit, num)) {
                return true;
            }
          }
          else if(visit[i] && i!=parent){
              // Loop Detect!
              return true;
          }
      }
      return false;
  }
  
    // Function to detect cycle in an undirected graph.
    bool isCycle(int V, vector<int> adj[]) {
        vector<bool> visit(V, false);

        for(int i=0; i<V; i++){
            if(visit[i]==false && dfs(i, adj, visit, -1)){
                return true;
            }
        }
        return false;
    }

Find the number of islands

問題

Grid上の1の塊の個数を数える問題。dfs()を呼ぶと１の塊1個がすべてゼロに置き換わるので、それを何回実行するか数え上げればよい。

    void dfs(int x, int y, vector<vector<char>>& grid){
        if(x<0 || y<0 || x>=grid.size() || y>=grid[x].size()){
            return;
        }
        
        if(grid[x][y]=='0'){
            return;
        }
        //for(int i=0; i<grid.size(); i++){
        //    for(int j=0; j<grid[i].size(); j++){
        //        cout<<grid[i][j];
        //    }
        //    cout<<endl;
        //}
        //cout<<"----"<<endl;
        
        grid[x][y]='0';
        
        int dict[8][2]={{1,1}, {1,-1}, {-1,1}, {-1,-1},
                        {0,1}, {0,-1}, {1, 0}, {-1,0}};
        
        for(int i=0; i<8; i++){
            dfs(x+dict[i][0], y+dict[i][1], grid);
        }
    }
    // Function to find the number of islands.
    int numIslands(vector<vector<char>>& grid) {
        // Code here
        int res=0;
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[i].size(); j++){
                if(grid[i][j]=='1'){
                    dfs(i, j, grid);
                    res++;
                }
            }
        }
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️