Graphs — Fundamentals & Traversals

int n = 6;  // Number of vertices (0-indexed: 0..n-1)
 
// Unweighted undirected graph
vector<vector<int>> adj(n);
adj[0].push_back(1); adj[1].push_back(0);  // Edge 0-1 (both directions)
adj[0].push_back(2); adj[2].push_back(0);
adj[1].push_back(3); adj[3].push_back(1);
 
// Weighted directed graph
vector<vector<pair<int,int>>> wadj(n);   // {neighbor, weight}
wadj[0].push_back({1, 5});   // Edge 0→1 with weight 5
wadj[0].push_back({2, 3});   // Edge 0→2 with weight 3
wadj[1].push_back({3, 2});   // Edge 1→3 with weight 2
 
// Build from edge list input
int edges; cin >> n >> edges;
vector<vector<int>> g(n);
for (int i = 0; i < edges; i++) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);  // Remove for directed graph
}

int n = 6;
vector<vector<int>> mat(n, vector<int>(n, 0));
 
mat[0][1] = mat[1][0] = 1;   // Unweighted undirected
mat[0][1] = 5;                // Directed weighted: 0→1 with weight 5
 
// Check if edge exists: O(1)
if (mat[u][v]) { /* edge exists */ }
 
// All neighbors of u: O(n) scan
for (int v = 0; v < n; v++)
    if (mat[u][v]) process(u, v);

// Unweighted
vector<pair<int,int>> edges = {{0,1},{0,2},{1,3},{2,3},{3,4}};
 
// Weighted (for Kruskal's MST)
vector<tuple<int,int,int>> wedges;  // {weight, u, v}
wedges.push_back({5, 0, 1});
wedges.push_back({3, 0, 2});
sort(wedges.begin(), wedges.end());  // Sort by weight

vector<int> bfs(int start, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);    // -1 = unvisited
    queue<int> q;
 
    dist[start] = 0;
    q.push(start);              // Mark visited WHEN ENQUEUING (not dequeuing!)
 
    while (!q.empty()) {
        int u = q.front(); q.pop();
 
        for (int v : adj[u]) {
            if (dist[v] == -1) {       // Not yet visited
                dist[v] = dist[u] + 1;
                q.push(v);             // Mark here
            }
        }
    }
    return dist;
}
// Time: O(V + E), Space: O(V)
// dist[v] = shortest path from start to v (-1 if unreachable)

void bfsLayers(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;
    int level = 0;
 
    while (!q.empty()) {
        int sz = q.size();          // Snapshot: all nodes at current level
        for (int i = 0; i < sz; i++) {
            int u = q.front(); q.pop();
            process(u, level);
            for (int v : adj[u])
                if (!visited[v]) { visited[v] = true; q.push(v); }
        }
        level++;
    }
}

// Shortest path in a grid from src to dst
// 0 = open, 1 = blocked
int bfsGrid(vector<vector<int>>& grid, pair<int,int> src, pair<int,int> dst) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    queue<pair<int,int>> q;
 
    auto [sr, sc] = src;
    dist[sr][sc] = 0;
    q.push(src);
 
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (r == dst.first && c == dst.second) return dist[r][c];
 
        for (int d = 0; d < 4; d++) {
            int nr = r+dx[d], nc = c+dy[d];
            if (nr>=0 && nr<R && nc>=0 && nc<C
                && grid[nr][nc]==0 && dist[nr][nc]==-1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return -1;
}
// Time: O(R × C), Space: O(R × C)

vector<bool> visited;
vector<vector<int>> adj;
 
void dfs(int u) {
    visited[u] = true;
    process(u);                     // Pre-order processing
 
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
    // Post-order processing here (used in topological sort, SCC)
}
 
// Run from every unvisited node (for disconnected graphs)
void dfsAll(int n) {
    visited.assign(n, false);
    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(i);
}
// Time: O(V + E), Space: O(V) — call stack depth ≤ V

int timer = 0;
vector<int> disc, finish;  // disc[u] = discovery time, finish[u] = finish time
 
void dfs(int u) {
    disc[u] = ++timer;   // Discovered
    visited[u] = true;
 
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
 
    finish[u] = ++timer; // Finished (all neighbors processed)
}
// disc[u] < disc[v] < finish[v] < finish[u] → v is in DFS subtree of u
// Used in: SCC (Kosaraju's), bridge/articulation point finding

void dfsIterative(int start, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;
 
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        process(u);
 
        // Push neighbors in reverse order to process them in original order
        for (int i = adj[u].size()-1; i >= 0; i--)
            if (!visited[adj[u][i]]) st.push(adj[u][i]);
    }
}
// Note: iterative DFS may visit nodes in different order than recursive DFS
// The key difference: recursive pushes implicitly (call stack), iterative explicitly

bool hasCycleUndirected(int u, int parent, vector<bool>& visited,
                         vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycleUndirected(v, u, visited, adj)) return true;
        } else if (v != parent) {
            return true;    // Visited neighbor that's not our parent → cycle!
        }
    }
    return false;
}
 
bool detectCycleUndirected(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++)
        if (!visited[i])
            if (hasCycleUndirected(i, -1, visited, adj)) return true;
    return false;
}
// Time: O(V + E), Space: O(V)
 
// Warning: Caveat: parent tracking doesn't work for multi-edges (parallel edges)
// Use edge index or DSU for multi-graphs

// Returns true if cycle detected
bool dfsDirected(int u, vector<int>& color, vector<vector<int>>& adj) {
    color[u] = 1;   // GRAY: mark as in-progress
 
    for (int v : adj[u]) {
        if (color[v] == 1) return true;    // GRAY → back edge → CYCLE!
        if (color[v] == 0)                 // WHITE → unvisited → recurse
            if (dfsDirected(v, color, adj)) return true;
        // BLACK → already fully processed → safe (cross/forward edge)
    }
 
    color[u] = 2;   // BLACK: fully processed
    return false;
}
 
bool hasCycleDirected(int n, vector<vector<int>>& adj) {
    vector<int> color(n, 0);   // All WHITE initially
    for (int i = 0; i < n; i++)
        if (color[i] == 0)
            if (dfsDirected(i, color, adj)) return true;
    return false;
}
// Time: O(V + E), Space: O(V)

vector<int> topoSort_Kahn(int n, vector<vector<int>>& adj) {
    vector<int> inDegree(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) inDegree[v]++;
 
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) q.push(i);
 
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }
 
    if ((int)order.size() != n) return {};  // Cycle detected!
    return order;
}
// Time: O(V + E), Space: O(V)
 
/*
  Graph: 0→1→3, 0→2→3, 2→4
  in-degrees: [0, 1, 1, 2, 1]
  Queue: [0]
  Process 0: order=[0], decrease 1 and 2's in-degree → queue=[1,2]
  Process 1: order=[0,1], decrease 3's in-degree (now 1) → queue=[2]
  Process 2: order=[0,1,2], decrease 3(now 0) and 4(now 0) → queue=[3,4]
  Process 3: order=[0,1,2,3] → queue=[4]
  Process 4: order=[0,1,2,3,4]
  Valid topological order!
*/

void dfsTopoSort(int u, vector<bool>& visited, stack<int>& st,
                 vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfsTopoSort(v, visited, st, adj);
    st.push(u);   // Push AFTER all neighbors processed (post-order)
}
 
vector<int> topoSort_DFS(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    stack<int> st;
 
    for (int i = 0; i < n; i++)
        if (!visited[i]) dfsTopoSort(i, visited, st, adj);
 
    vector<int> order;
    while (!st.empty()) { order.push_back(st.top()); st.pop(); }
    return order;
}
// Time: O(V + E), Space: O(V)
// Note: doesn't detect cycles directly — use color-based DFS (18.5) for that

// LC 207: Can you finish all courses given prerequisites?
// = Detect cycle in directed graph of prerequisites
 
bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    for (auto& p : prerequisites) adj[p[1]].push_back(p[0]);
 
    vector<int> inDeg(n, 0);
    for (int u = 0; u < n; u++) for (int v : adj[u]) inDeg[v]++;
 
    queue<int> q;
    for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.push(i);
 
    int processed = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); processed++;
        for (int v : adj[u]) if (--inDeg[v] == 0) q.push(v);
    }
    return processed == n;  // All processed → no cycle → can finish
}

int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    int components = 0;
 
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;
            // BFS from i to visit entire component
            queue<int> q;
            q.push(i); visited[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u])
                    if (!visited[v]) { visited[v] = true; q.push(v); }
            }
        }
    }
    return components;
}
// Time: O(V + E), Space: O(V)

vector<int> componentOf(int n, vector<vector<int>>& adj) {
    vector<int> comp(n, -1);
    int compId = 0;
 
    for (int i = 0; i < n; i++) {
        if (comp[i] != -1) continue;
        // BFS from i
        queue<int> q;
        q.push(i); comp[i] = compId;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u])
                if (comp[v] == -1) { comp[v] = compId; q.push(v); }
        }
        compId++;
    }
    return comp;   // comp[v] = component ID of vertex v
}

// Count connected regions of 1s in a grid (Number of Islands)
int numIslands(vector<vector<char>>& grid) {
    int R = grid.size(), C = grid[0].size(), count = 0;
 
    function<void(int,int)> dfs = [&](int r, int c) {
        if (r<0||r>=R||c<0||c>=C||grid[r][c]!='1') return;
        grid[r][c] = '0';    // Mark visited in-place
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    };
 
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == '1') { count++; dfs(r, c); }
    return count;
}
// Time: O(R × C), Space: O(R × C) recursion stack worst case

vector<vector<int>> kosaraju(int n, vector<vector<int>>& adj) {
    // Step 1: DFS to get finish order
    vector<bool> visited(n, false);
    stack<int> finishOrder;
 
    function<void(int)> dfs1 = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) if (!visited[v]) dfs1(v);
        finishOrder.push(u);   // Push AFTER all descendants
    };
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(i);
 
    // Step 2: Build transposed graph
    vector<vector<int>> radj(n);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) radj[v].push_back(u);
 
    // Step 3: DFS on transposed in reverse finish order
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
 
    function<void(int, vector<int>&)> dfs2 = [&](int u, vector<int>& scc) {
        visited[u] = true;
        scc.push_back(u);
        for (int v : radj[u]) if (!visited[v]) dfs2(v, scc);
    };
 
    while (!finishOrder.empty()) {
        int u = finishOrder.top(); finishOrder.pop();
        if (!visited[u]) {
            sccs.push_back({});
            dfs2(u, sccs.back());
        }
    }
    return sccs;
}
// Time: O(V + E), Space: O(V + E) for transposed graph

bool isBipartite(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);   // -1 = uncolored
 
    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;
 
        queue<int> q;
        q.push(start);
        color[start] = 0;
 
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];   // Assign opposite color
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;   // Same color → not bipartite!
                }
            }
        }
    }
    return true;
}
// Time: O(V + E), Space: O(V)

bool dfsColor(int u, int c, vector<int>& color, vector<vector<int>>& adj) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == -1) {
            if (!dfsColor(v, 1-c, color, adj)) return false;
        } else if (color[v] == c) {
            return false;   // Same color as current → not bipartite
        }
    }
    return true;
}
 
bool isBipartiteDFS(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);
    for (int i = 0; i < n; i++)
        if (color[i] == -1)
            if (!dfsColor(i, 0, color, adj)) return false;
    return true;
}

// Find minimum distance from any source (set of sources) to each node
vector<int> multiSourceBFS(int n, vector<vector<int>>& adj,
                            vector<int>& sources) {
    vector<int> dist(n, -1);
    queue<int> q;
 
    for (int s : sources) {
        dist[s] = 0;
        q.push(s);
    }
 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}
// Applications: 01-Matrix (distance to nearest 0), Rotting Oranges,
//               Walls and Gates, spreading fire/infection problems

vector<int> zeroOneBFS(int start, int n,
                        vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight)} where weight ∈ {0, 1}
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
 
    dist[start] = 0;
    dq.push_front(start);
 
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);   // 0-weight: higher priority
                else        dq.push_back(v);     // 1-weight: lower priority
            }
        }
    }
    return dist;
}
// Time: O(V + E), Space: O(V)

int numIslands(vector<vector<char>>& grid) {
    int R=grid.size(), C=grid[0].size(), count=0;
    function<void(int,int)> dfs=[&](int r,int c) {
        if(r<0||r>=R||c<0||c>=C||grid[r][c]!='1') return;
        grid[r][c]='0';
        dfs(r+1,c);dfs(r-1,c);dfs(r,c+1);dfs(r,c-1);
    };
    for(int r=0;r<R;r++) for(int c=0;c<C;c++)
        if(grid[r][c]=='1'){count++;dfs(r,c);}
    return count;
}
// Time: O(R×C), Space: O(R×C) recursion

int findCircleNum(vector<vector<int>>& isConnected) {
    int n=isConnected.size(), count=0;
    vector<bool> visited(n,false);
    function<void(int)> dfs=[&](int u) {
        visited[u]=true;
        for(int v=0;v<n;v++) if(!visited[v]&&isConnected[u][v]) dfs(v);
    };
    for(int i=0;i<n;i++) if(!visited[i]){count++;dfs(i);}
    return count;
}
// Time: O(n²), Space: O(n)

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    vector<int> inDeg(n,0);
    for(auto& p:prerequisites){adj[p[1]].push_back(p[0]);inDeg[p[0]]++;}
    queue<int> q;
    for(int i=0;i<n;i++) if(inDeg[i]==0) q.push(i);
    int cnt=0;
    while(!q.empty()){
        int u=q.front();q.pop();cnt++;
        for(int v:adj[u]) if(--inDeg[v]==0) q.push(v);
    }
    return cnt==n;
}
// Time: O(V+E), Space: O(V+E)

vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    vector<int> inDeg(n,0);
    for(auto& p:prerequisites){adj[p[1]].push_back(p[0]);inDeg[p[0]]++;}
    queue<int> q;
    for(int i=0;i<n;i++) if(inDeg[i]==0) q.push(i);
    vector<int> order;
    while(!q.empty()){
        int u=q.front();q.pop();order.push_back(u);
        for(int v:adj[u]) if(--inDeg[v]==0) q.push(v);
    }
    return (int)order.size()==n ? order : vector<int>{};
}
// Time: O(V+E), Space: O(V+E)

Node* cloneGraph(Node* node) {
    if(!node) return nullptr;
    unordered_map<Node*,Node*> cloned;
    queue<Node*> q;
    q.push(node);
    cloned[node] = new Node(node->val);
 
    while(!q.empty()){
        Node* u=q.front();q.pop();
        for(Node* nb:u->neighbors){
            if(!cloned.count(nb)){
                cloned[nb]=new Node(nb->val);
                q.push(nb);
            }
            cloned[u]->neighbors.push_back(cloned[nb]);
        }
    }
    return cloned[node];
}
// Time: O(V+E), Space: O(V)

bool isBipartite(vector<vector<int>>& graph) {
    int n=graph.size();
    vector<int> color(n,-1);
    for(int start=0;start<n;start++){
        if(color[start]!=-1) continue;
        queue<int> q;
        q.push(start); color[start]=0;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int v:graph[u]){
                if(color[v]==-1){color[v]=1-color[u];q.push(v);}
                else if(color[v]==color[u]) return false;
            }
        }
    }
    return true;
}
// Time: O(V+E), Space: O(V)

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int R=heights.size(), C=heights[0].size();
    vector<vector<bool>> pac(R,vector<bool>(C,false));
    vector<vector<bool>> atl(R,vector<bool>(C,false));
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
 
    // BFS from ocean boundaries INWARD (reverse flow)
    auto bfs=[&](queue<pair<int,int>>& q, vector<vector<bool>>& reach) {
        while(!q.empty()){
            auto[r,c]=q.front();q.pop();
            for(int d=0;d<4;d++){
                int nr=r+dx[d],nc=c+dy[d];
                if(nr>=0&&nr<R&&nc>=0&&nc<C&&!reach[nr][nc]
                   &&heights[nr][nc]>=heights[r][c]){
                    reach[nr][nc]=true;
                    q.push({nr,nc});
                }
            }
        }
    };
 
    queue<pair<int,int>> pq, aq;
    for(int r=0;r<R;r++){
        pac[r][0]=true; pq.push({r,0});
        atl[r][C-1]=true; aq.push({r,C-1});
    }
    for(int c=0;c<C;c++){
        pac[0][c]=true; pq.push({0,c});
        atl[R-1][c]=true; aq.push({R-1,c});
    }
    bfs(pq,pac); bfs(aq,atl);
 
    vector<vector<int>> result;
    for(int r=0;r<R;r++)
        for(int c=0;c<C;c++)
            if(pac[r][c]&&atl[r][c]) result.push_back({r,c});
    return result;
}
// Time: O(R×C), Space: O(R×C)

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    int n=graph.size();
    vector<vector<int>> result;
    vector<int> path={0};
    function<void(int)> dfs=[&](int u){
        if(u==n-1){result.push_back(path);return;}
        for(int v:graph[u]){
            path.push_back(v);
            dfs(v);
            path.pop_back();
        }
    };
    dfs(0);
    return result;
}
// Time: O(2^n × n) — exponential paths possible
// Space: O(n) depth

// Approach: Reverse graph + Kahn's topological sort
// Safe nodes = nodes that reach terminal without cycle = nodes with out-degree 0
// in the original = nodes with in-degree 0 in the REVERSED graph
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int n=graph.size();
    vector<vector<int>> radj(n);
    vector<int> outDeg(n,0);
 
    for(int u=0;u<n;u++){
        outDeg[u]=graph[u].size();
        for(int v:graph[u]) radj[v].push_back(u);
    }
 
    queue<int> q;
    for(int i=0;i<n;i++) if(outDeg[i]==0) q.push(i);
 
    vector<bool> safe(n,false);
    while(!q.empty()){
        int u=q.front();q.pop();
        safe[u]=true;
        for(int v:radj[u])
            if(--outDeg[v]==0) q.push(v);
    }
 
    vector<int> result;
    for(int i=0;i<n;i++) if(safe[i]) result.push_back(i);
    return result;
}
// Time: O(V+E), Space: O(V+E)

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if(n==1) return {0};
    vector<vector<int>> adj(n);
    vector<int> deg(n,0);
    for(auto& e:edges){
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
        deg[e[0]]++; deg[e[1]]++;
    }
 
    queue<int> leaves;
    for(int i=0;i<n;i++) if(deg[i]==1) leaves.push(i);
 
    int remaining=n;
    while(remaining>2){
        int sz=leaves.size();
        remaining-=sz;
        for(int i=0;i<sz;i++){
            int leaf=leaves.front();leaves.pop();
            for(int nb:adj[leaf])
                if(--deg[nb]==1) leaves.push(nb);
        }
    }
    vector<int> result;
    while(!leaves.empty()){result.push_back(leaves.front());leaves.pop();}
    return result;
}
// Time: O(V), Space: O(V)

string alienOrder(vector<string>& words) {
    unordered_map<char,unordered_set<char>> adj;
    unordered_map<char,int> inDeg;
 
    // Initialize all characters with in-degree 0
    for(auto& w:words) for(char c:w) inDeg[c]=0;
 
    // Extract ordering from adjacent word pairs
    for(int i=0;i<(int)words.size()-1;i++){
        string& a=words[i], &b=words[i+1];
        int len=min(a.size(),b.size());
        bool found=false;
        for(int j=0;j<(int)len;j++){
            if(a[j]!=b[j]){
                if(!adj[a[j]].count(b[j])){
                    adj[a[j]].insert(b[j]);
                    inDeg[b[j]]++;
                }
                found=true; break;
            }
        }
        // Invalid: word a is prefix of b but longer → impossible
        if(!found && a.size()>b.size()) return "";
    }
 
    // Kahn's topological sort
    queue<char> q;
    for(auto& [c,d]:inDeg) if(d==0) q.push(c);
 
    string order;
    while(!q.empty()){
        char c=q.front();q.pop();
        order+=c;
        for(char nb:adj[c])
            if(--inDeg[nb]==0) q.push(nb);
    }
    return order.size()==inDeg.size() ? order : "";
}
// Time: O(C) where C = total characters, Space: O(U + min(U², N)) where U=unique chars

// Hierholzer's algorithm for Eulerian path
vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, priority_queue<string,
                  vector<string>, greater<string>>> adj;
 
    for(auto& t:tickets) adj[t[0]].push(t[1]);
 
    vector<string> result;
    stack<string> st;
    st.push("JFK");
 
    while(!st.empty()){
        string u=st.top();
        if(!adj[u].empty()){
            st.push(adj[u].top());
            adj[u].pop();
        } else {
            result.push_back(u);
            st.pop();
        }
    }
    reverse(result.begin(),result.end());
    return result;
}
// Time: O(E log E) — priority queue for lexicographic order
// Space: O(V + E)