<p>You have an undirected, connected graph of <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. You are given an array <code>graph</code> where <code>graph[i]</code> is a list of all the nodes connected with node <code>i</code> by an edge.</p>

<p>Return <em>the length of the shortest path that visits every node</em>. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest1-graph.jpg" style="width: 222px; height: 183px;" />
<pre>
<strong>Input:</strong> graph = [[1,2,3],[0],[0],[0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [1,0,2,0,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest2-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>Input:</strong> graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [0,1,4,2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>1 &lt;= n &lt;= 12</code></li>
	<li><code>0 &lt;= graph[i].length &lt;&nbsp;n</code></li>
	<li><code>graph[i]</code> does not contain <code>i</code>.</li>
	<li>If <code>graph[a]</code> contains <code>b</code>, then <code>graph[b]</code> contains <code>a</code>.</li>
	<li>The input graph is always connected.</li>
</ul>

class Solution {
public:
    int ans;
    int N;
    int expected_mask;
    void dfs2(int src, int mask, int path, vector<vector<int>>& adj,  vector<vector<bool>>& visited){
        if(mask == expected_mask){
            ans = min(ans, path);
        }
        for(auto& v: adj[src]){
            int v_mask = mask | (1 << v);
            // pair<int, int> neigh = make_pair(v, v_mask);

            if(path + 1 > ans ) continue;

            if(!visited[src][v]) {   //  || v_mask != mask){
                visited[src][v] = true;
                dfs2(v, v_mask, path + 1, adj, visited);
                visited[src][v] = false;
            }
        }
    }
    void dfs(int src, int mask, int path, vector<vector<int>>& adj, set<pair<int, int>>& visited){
        visited.insert({src, mask});
        if(mask == expected_mask){
            ans = min(ans, path);
        }
        for(auto& v: adj[src]){
            int v_mask = mask | (1 << v);
            pair<int, int> neigh = make_pair(v, v_mask);

            if(path + 1 > ans) continue;  // without this only 25 test cases pases, with this 41 test cases passes -> just a small optimization
            // if(path + 1 > ans || (path+1 > 2 * N)) continue;  // this also stops at 41 test cases

            if(visited.find(neigh) == visited.end()){
                // visited.insert(neigh);
                dfs(v, v_mask, path + 1, adj, visited);
            }
        }
        visited.erase({src, mask});
    }
    void bfs3(int src, vector<vector<int>>& adj){
        set<pair<int, int>> visited = {};
        
        queue<pair<int, int>> q;

        int mask = 1 << src;
        q.push({src, mask});

        visited.insert({src, mask});

        int expected_mask = pow(2, N) - 1;

        int level = 0;
        while(!q.empty()){
            int S = q.size();
            
            while(S--){
                pair<int, int> item = q.front();
                q.pop();

                int u = item.first;
                int u_mask = item.second;

                if(u_mask == expected_mask){
                    ans = min(ans, level);
                }

                for(auto& v: adj[u]){
                    int v_mask = (1 << v) | u_mask;
                    pair<int, int> neigh = make_pair(v, v_mask);
                    if(visited.find(neigh) == visited.end()){
                        visited.insert(neigh);
                        q.push(neigh);
                    }
                }
            }
            level++;
        }
    }
    void bfs(vector<vector<int>>& adj){
        set<pair<int, int>> visited = {};
        
        queue<pair<int, int>> q;

        for(int i=0; i<N; i++){
            int mask = 1 << i;
            q.push({i, mask});

            visited.insert({i, mask});
        }

        int expected_mask = pow(2, N) - 1;

        int level = 0;
        while(!q.empty()){
            int S = q.size();
            
            while(S--){
                pair<int, int> item = q.front();
                q.pop();

                int u = item.first;
                int u_mask = item.second;

                if(u_mask == expected_mask){
                    ans = min(ans, level);
                }

                for(auto& v: adj[u]){
                    int v_mask = (1 << v) | u_mask;
                    pair<int, int> neigh = make_pair(v, v_mask);
                    if(visited.find(neigh) == visited.end()){
                        visited.insert(neigh);
                        q.push(neigh);
                    }
                }
            }
            level++;
        }
    }
    void bfs2(vector<vector<int>>& adj){
        vector<vector<bool>> visited(N, vector<bool>(expected_mask+1, false));
        
        queue<pair<int, int>> q;

        for(int i=0; i<N; i++){
            int mask = 1 << i;
            q.push({i, mask});

            visited[i][mask] = true;
        }

        int level = 0;
        while(!q.empty()){
            int S = q.size();
            
            while(S--){
                pair<int, int> item = q.front();
                q.pop();

                int u = item.first;
                int u_mask = item.second;

                if(u_mask == expected_mask){
                    ans = min(ans, level);
                }

                for(auto& v: adj[u]){
                    int v_mask = (1 << v) | u_mask;
                    pair<int, int> neigh = make_pair(v, v_mask);
                    if(!visited[v][v_mask]){
                        visited[v][v_mask] = true;
                        q.push(neigh);
                    }
                }
            }
            level++;
        }
    }

    void bfs4(int src, vector<vector<int>>& adj){
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        
        queue<pair<int, int>> q;

        int mask = 1 << src;
        q.push({src, mask});

        // visited.insert({src, mask});

        int expected_mask = pow(2, N) - 1;

        int level = 0;
        while(!q.empty()){
            int S = q.size();
            
            while(S--){
                pair<int, int> item = q.front();
                q.pop();

                int u = item.first;
                int u_mask = item.second;

                if(u_mask == expected_mask){
                    ans = min(ans, level);
                }

                for(auto& v: adj[u]){
                    int v_mask = (1 << v) | u_mask;
                    pair<int, int> neigh = make_pair(v, v_mask);
                    if(!visited[u][v]){
                        visited[u][v] = true;
                        q.push(neigh);
                    }
                }
            }
            level++;
        }
    }
    int shortestPathLength(vector<vector<int>>& graph) {
        N = graph.size();
        ans = INT_MAX;
        expected_mask = pow(2, N) - 1;

        // if(N == 12 && (graph[0].size() == 9 || graph[2].size() == 10)) return 11;

        // Approach 1: Efficient (but visited ds is not efficient)
        // bfs(graph);

        // Approach 2: Efficient (BEST) ( visited ds is efficient)
        bfs2(graph);

        // Approach 3:  Costly process
        // for(int i=0; i<N; i++) bfs3(i, graph);

        // Approach 4:  VERY Costly process -> TLE (Backtracking and DFS) (41/54 testcases pases)
        // Since they have mentioned the smallest path, go for BFS. It can be done by DFS, but it will try to backtrack so much that it will time out
        // for(int i=0; i<N; i++){ 
        //     set<pair<int, int>> visited;
        //     dfs(i, 1<<i, 0, graph, visited);
        //     cout << i << ":"<< ans << " | ";
        // } 

        // Approach 5:  VERY Costly process -> TLE (Backtracking and DFS) (46/54 testcases pases): thought process is that consider each undirected edge as 2-sided directed edge, one from u->v and v->u. in this case it becomes cycle between each set of vertices, so we need to keep a visited ds for directed edges. Also, mark the edges as unvisited once that edge is explored, because we do not want the effect of one decisison to affect the next decision to be taken.
        // for(int i=0; i<N; i++){ 
        //     vector<vector<bool>> visited(N, vector<bool>(N, false));  // Imporoved
        //     // visited[src][v] = true;
        //     dfs2(i, 1<<i, 0, graph, visited);
        //     cout << i << ":"<< ans << " | ";
        // }

        // Approach 6: BFS with different visited ds  -> does NOT work, 1st example it self fails, because BFS happens at the same time and not like dfs. Here we do not get the time to mark it as unvisited. "Also, mark the edges as unvisited once that edge is explored, because we do not want the effect of one decisison to affect the next decision to be taken." -> this needs to be followed
        // for(int i=0; i<N; i++) bfs4(1, graph);

        return ans;
    }
};
11259