<p>There is a <strong>bi-directional</strong> graph with <code>n</code> vertices, where each vertex is labeled from <code>0</code> to <code>n - 1</code> (<strong>inclusive</strong>). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> denotes a bi-directional edge between vertex <code>u<sub>i</sub></code> and vertex <code>v<sub>i</sub></code>. Every vertex pair is connected by <strong>at most one</strong> edge, and no vertex has an edge to itself.</p>

<p>You want to determine if there is a <strong>valid path</strong> that exists from vertex <code>source</code> to vertex <code>destination</code>.</p>

<p>Given <code>edges</code> and the integers <code>n</code>, <code>source</code>, and <code>destination</code>, return <code>true</code><em> if there is a <strong>valid path</strong> from </em><code>source</code><em> to </em><code>destination</code><em>, or </em><code>false</code><em> otherwise</em><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> There are two paths from vertex 0 to vertex 2:
- 0 &rarr; 1 &rarr; 2
- 0 &rarr; 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no path from vertex 0 to vertex 5.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>
	<li>There are no duplicate edges.</li>
	<li>There are no self edges.</li>
</ul>

class Solution {
private:
    vector<int> makeVecNodes(const int s, vector<vector<int>>& edges, const int exclude) {
        vector<int> children;

        if (exclude<=-1) {
            for (int iEdge=0; iEdge<=edges.size()-1; iEdge++) {
                vector<int> edge_uv = edges[iEdge];

                if (edge_uv[0]==s) {children.push_back(edge_uv[1]);}
                else {
                    if (edge_uv[1]==s) {children.push_back(edge_uv[0]);}
                }
            }
        }
        else { // excluded node is valid
            for (int iEdge=0; iEdge<=edges.size()-1; iEdge++) {
                vector<int> edge_uv = edges[iEdge];
                
                if (exclude!=edge_uv[0] && exclude!=edge_uv[1]){
                    if (edge_uv[0]==s) {children.push_back(edge_uv[1]);}
                    else {
                        if (edge_uv[1]==s) {children.push_back(edge_uv[0]);}
                    }
                }
            }
        }

        return children;
    } // makeVecNodes()

    vector<int>* makeNestVecNodes(const int n, vector<vector<int>>& edges) {
        vector<int>* nestVecNodes = new vector<int>[n];

        vector<vector<int>>::iterator edge_itr;
        vector<int>::iterator edgedge_itr;

        for (edge_itr=edges.begin(); edge_itr<edges.end(); edge_itr++) {
            vector<int> e = *edge_itr; // e.size()==2

            nestVecNodes[e[0]].push_back(e[1]);
            nestVecNodes[e[1]].push_back(e[0]);
        }
        
        return nestVecNodes;
    } // makeNestVecNodes()


public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if (n<=1 || source==destination) {return true;}

        // Depth first? 

        // make map (size-n array of vector<int>)
        vector<int>* mapNodes = makeNestVecNodes(n, edges);
        cout << "map made.\n";

        int v; // current node
        bool deeper;
        // make a list (vector) of s(ource): [n1,n2,n3,...] connected to s
        vector<int> layer1 = mapNodes[source];

        // stack of node, arr_explored[] = 0 except arr[0]=1
        stack<int> branch;
        int* explore = new int[n];
        for (int i=0; i<=n-1; i++) {explore[i]=0;}
        explore[source]=1;

        v = source;

        // loop [n1,n2,n3,...] (start while loop later to simplify while exec)
        vector<int>::iterator layer1_itr;

        vector<int> layer_2;

        for (layer1_itr=layer1.begin(); layer1_itr<layer1.end(); layer1_itr++) {
            v = *layer1_itr;

            if (v==destination) {return true;}
            branch.push(v); // *layer1_itr;

            if (explore[v]==0) {
                explore[v]=1;
                //layer_2 = makeVecNodes(v, edges, source); 
                layer_2 = mapNodes[v];
                
                if (!layer_2.empty()) {
                    // check if nodes 1 layer deeper contain unexplored
                    vector<int>::iterator layer2_itr;
                    vector<int> to_erase; // remove visited nodes in adj list

                    deeper = false;
                    for (layer2_itr=layer_2.begin(); layer2_itr<layer_2.end();layer2_itr++) {
                        if (explore[*layer2_itr]==0) {
                            deeper = true; break;
                        }
                        else {to_erase.push_back(layer2_itr-layer_2.begin());} 
                    }

                    for (vector<int>::iterator erase_itr=to_erase.begin(); erase_itr<to_erase.end();
                    erase_itr++) {cout << to_erase[*erase_itr] << ' ';}
                    cout <<endl;

                    sort(to_erase.begin(), to_erase.end());
                    int offset = 0;
                    vector<int>::iterator map_0itr = mapNodes[v].begin();
                    for (vector<int>::iterator erase_itr=to_erase.begin(); erase_itr<to_erase.end();
                    erase_itr++) {
                        mapNodes[v].erase(map_0itr+(*erase_itr-offset));
                        offset++; map_0itr = mapNodes[v].begin();
                    }

                    if (deeper) { // layer 2+
                        v = *layer2_itr; // 1st unexplored node found in above for loop
                        if (v==destination) {return true;}

                        vector<int> layer_m;
                        vector<int>::iterator layerm_itr;

                        int layer_ctr = 2;

                        while (true) {
                            //cout << "v=" << v << ", debugging is so hard on LC\n";
                            if (explore[v]==0) {
                                explore[v] = 1;
                                //layer_m = makeVecNodes(v, edges, branch.top());
                                layer_m = mapNodes[v];

                                branch.push(v);
                                
                                deeper = false;
                                to_erase.clear();

                                for (layerm_itr=layer_m.begin(); layerm_itr<layer_m.end();
                                    layerm_itr++) {
                                    if (explore[*layerm_itr]==0) {
                                        deeper = true; break;
                                    }
                                    else {to_erase.push_back(layerm_itr-layer_m.begin());} 
                                }

                                //removeExploredFromMap(to_erase, mapNodes, v);
                                sort(to_erase.begin(), to_erase.end());
                                int offset = 0;
                                vector<int>::iterator map_0itr = mapNodes[v].begin();
                                for (vector<int>::iterator erase_itr=to_erase.begin(); 
                                erase_itr<to_erase.end(); erase_itr++) {
                                    mapNodes[v].erase(map_0itr+(*erase_itr-offset));
                                    offset++; map_0itr = mapNodes[v].begin();
                                }
                                
                                if (deeper){
                                    v = *layerm_itr; 
                                    if (v==destination) {return true;}
                                }
                                else { // go back up, pop stack
                                       // try to find sibling
                                    cout << "going back up: v=" << v;
                                    while (!branch.empty()){
                                        branch.pop(); 
                                        if (branch.empty()) {goto nextLayer1;}
                                        v = branch.top(); // parent
                                        cout << ", parent=" << v << endl;
                                        //layer_m = makeVecNodes(v, edges, -99);
                                        layer_m = mapNodes[v];
                                        to_erase.clear();
                                        
                                        deeper = false;
                                        for (layerm_itr=layer_m.begin(); layerm_itr<layer_m.end();
                                             layerm_itr++) {
                                            if (explore[*layerm_itr]==0) {
                                                deeper = true; break;
                                            }
                                            else {to_erase.push_back(layerm_itr-layer_m.begin());}
                                        }

                                        //removeExploredFromMap(to_erase, mapNodes, v);
                                        sort(to_erase.begin(), to_erase.end());
                                        int offset = 0;
                                        vector<int>::iterator map_0itr = mapNodes[v].begin();
                                        for (vector<int>::iterator erase_itr=to_erase.begin(); 
                                        erase_itr<to_erase.end(); erase_itr++) {
                                            mapNodes[v].erase(map_0itr+(*erase_itr-offset));
                                            offset++; map_0itr = mapNodes[v].begin();
                                        }

                                        if (deeper) {
                                            v = *layerm_itr;
                                            if (v==destination) {return true;}
                                            break; // stack nonempty
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            nextLayer1:;
        }
        //    if exp[ni]==0:
        //      mark explored
        //      make a map of ni:[ni1,ni2,...] except parent (the source)
        //      add ni to stack
        //      if ni1 exists, v = ni1, check v ?= dest; else continue;
        //      while true:
        //          if exp==0:
        //              add nj to stack, exp=1
        //              make map of nj: nj1, ... except parent (nj)
        //              if map has unexplored nodes: v = nj1, check v ?= dest
        //              else: 
        //                  while stack is nonempty:
        //                      v = parent (from stack), pop self, don't check v ?= dest
        //                      if there's sibling (check map) unexplored:
        //                          v = the sibling, check v ?= dest
        //                          break (while stack nonempty)

        delete [] mapNodes;
        delete [] explore;
        return false;
    }
};
310632