graph-algorithm-specialist

name	graph-algorithm-specialist
description	Guides graph algorithm mastery including BFS, DFS, shortest paths, minimum spanning trees, topological sort, and cycle detection with implementation patterns Use when the user asks about graph algorithm specialist, related techniques, best practices, or needs guidance in this domain. Do NOT use when the request is outside the scope of graph algorithm specialist or requires a different specialized skill.
license	Apache-2.0
metadata	{"author":"foundry-skills","version":"1.0.0","tags":"advanced competitive-programming guide beginner-friendly testing analysis networking parenting","category":"emerging-tech","subcategory":"competitive-programming","depends":"","disclaimer":"none","difficulty":"intermediate"}

Graph Algorithm Specialist

You are an expert competitive programming coach specializing in graph algorithms. You guide programmers through graph representations, BFS, DFS, shortest path algorithms, minimum spanning trees, topological sorting, cycle detection, and advanced graph techniques with rigorous complexity analysis.

When to Use

Use this skill when:

• User asks about graph algorithm specialist techniques or best practices
• User needs guidance on graph algorithm specialist concepts
• User wants to implement or improve their approach to graph algorithm specialist

Do NOT use when:

• The request falls outside the scope of graph algorithm specialist
• User needs a different specialized skill for their specific situation
• The topic requires professional consultation beyond general guidance

Graph Representation

Adjacency List (Preferred for Sparse Graphs)

// Unweighted graph
vector<vector<int>> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);  // Undirected

// Weighted graph
vector<vector<pair<int,int>>> adj(n);  // {neighbor, weight}
adj[u].push_back({v, w});

Representation Comparison

Representation	Space	Edge Query	Iterate Neighbors	Best For
Adjacency List	O(V+E)	O(degree)	O(degree)	Sparse graphs
Adjacency Matrix	O(V^2)	O(1)	O(V)	Dense, small V
Edge List	O(E)	O(E)	O(E)	Kruskal, sorting edges

Breadth-First Search (BFS)

Standard BFS (Shortest Path in Unweighted Graph)

// Time: O(V + E), Space: O(V)
vector<int> bfs(vector<vector<int>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    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;
}

Multi-Source BFS

// BFS from multiple sources simultaneously
// Time: O(V + E), Space: O(V)
vector<int> multiSourceBFS(vector<vector<int>>& adj, vector<int>& sources) {
    int n = adj.size();
    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;
}

0-1 BFS (Edges with Weight 0 or 1)

// Time: O(V + E), Space: O(V)
vector<int> bfs01(vector<vector<pair<int,int>>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    dist[src] = 0;
    dq.push_front(src);
    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);
                else dq.push_back(v);
            }
        }
    }
    return dist;
}

Depth-First Search (DFS)

Iterative DFS (Avoids Stack Overflow)

// Time: O(V + E), Space: O(V)
void dfs_iterative(vector<vector<int>>& adj, int src) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;
    st.push(src);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v : adj[u])
            if (!visited[v]) st.push(v);
    }
}

DFS with Entry/Exit Times

// For subtree queries. Time: O(V + E)
int timer = 0;
vector<int> tin, tout;

void dfs(vector<vector<int>>& adj, int u, int parent) {
    tin[u] = timer++;
    for (int v : adj[u])
        if (v != parent) dfs(adj, v, u);
    tout[u] = timer++;
}

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

Connected Components

// Time: O(V + E), Space: O(V)
int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    int components = 0;
    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) if (!visited[v]) dfs(v);
    };
    for (int i = 0; i < n; i++)
        if (!visited[i]) { dfs(i); components++; }
    return components;
}

Shortest Path Algorithms

Dijkstra's Algorithm

// Non-negative weights. Time: O((V + E) log V)
vector<long long> dijkstra(vector<vector<pair<int,int>>>& adj, int src) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Bellman-Ford Algorithm

// Handles negative weights, detects negative cycles
// Time: O(V * E), Space: O(V)
struct Edge { int from, to, weight; };

pair<vector<long long>, bool> bellmanFord(int n, vector<Edge>& edges, int src) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    bool hasNegCycle = false;
    for (auto& [u, v, w] : edges)
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) { hasNegCycle = true; break; }
    return {dist, hasNegCycle};
}

Floyd-Warshall (All-Pairs)

// Time: O(V^3), Space: O(V^2)
void floydWarshall(vector<vector<long long>>& dist, int n) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

Algorithm Selection Guide

Algorithm	Weights	Negative	Time	Use When
BFS	Unweighted	N/A	O(V+E)	Unit weights
0-1 BFS	0 or 1	No	O(V+E)	Binary weights
Dijkstra	Non-negative	No	O((V+E)logV)	General positive
Bellman-Ford	Any	Yes (detects)	O(VE)	Negative weights
Floyd-Warshall	Any	Yes (detects)	O(V^3)	Small V, all-pairs

Minimum Spanning Tree

Kruskal's Algorithm (Edge-based)

// Time: O(E log E), Space: O(V)
class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        return true;
    }
};

long long kruskal(int n, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    long long mstWeight = ;
     edgeCount = ;
     ( [w, u, v] : edges) {
         (uf.(u, v)) {
            mstWeight += w;
             (++edgeCount == n - ) ;
        }
    }
     mstWeight;
}

Prim's Algorithm (Vertex-based)

// Time: O((V + E) log V), Space: O(V)
long long prim(vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<bool> inMST(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});
    long long mstWeight = 0;
    int count = 0;
    while (!pq.empty() && count < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        mstWeight += w;
        count++;
        for (auto [v, wt] : adj[u])
            if (!inMST[v]) pq.push({wt, v});
    }
    return mstWeight;
}

Topological Sort

Kahn's Algorithm (BFS-based)

// Time: O(V + E). If order.size() < n, graph has a cycle.
vector<int> topologicalSort(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);
    }
    return order;
}

DFS-based Topological Sort

// Reverse post-order. Time: O(V + E)
vector<int> topoSortDFS(int n, vector<vector<int>>& adj) {
    vector<int> order, state(n, 0);
    bool hasCycle = false;
    function<void(int)> dfs = [&](int u) {
        if (hasCycle) return;
        state[u] = 1;
        for (int v : adj[u]) {
            if (state[v] == 1) { hasCycle = true; return; }
            if (state[v] == 0) dfs(v);
        }
        state[u] = 2;
        order.push_back(u);
    };
    for (int i = 0; i < n; i++) if (state[i] == 0) dfs(i);
    reverse(order.begin(), order.end());
    return order;
}

Cycle Detection

Directed Graph (DFS Coloring)

// Time: O(V + E)
bool hasCycleDirected(int n, vector<vector<int>>& adj) {
    vector<int> color(n, 0);
    function<bool(int)> dfs = [&](int u) -> bool {
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 1) return true;
            if (color[v] == 0 && dfs(v)) return true;
        }
        color[u] = 2;
        return false;
    };
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfs(i)) return true;
    return false;
}

Undirected Graph (Union-Find)

// Time: O(E * alpha(V))
bool hasCycleUndirected(int n, vector<pair<int,int>>& edges) {
    UnionFind uf(n);
    for (auto [u, v] : edges)
        if (uf.find(u) == uf.find(v)) return true;
        else uf.unite(u, v);
    return false;
}

Strongly Connected Components (Kosaraju)

// Time: O(V + E)
vector<vector<int>> kosaraju(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    vector<int> order;
    function<void(int)> dfs1 = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) if (!visited[v]) dfs1(v);
        order.push_back(u);
    };
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(i);

    vector<vector<int>> radj(n);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) radj[v].push_back(u);

    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
    function<void(int, vector<int>&)> dfs2 = [&](int u, vector<int>& comp) {
        visited[u] = true;
        comp.push_back(u);
        for (int v : radj[u]) if (!visited[v]) dfs2(v, comp);
    };
    for (int i = n - ; i >= ; i--) {
         u = order[i];
         (!visited[u]) { sccs.({}); (u, sccs.()); }
    }
     sccs;
}

Common Pitfalls

Mistake	Fix
Dijkstra with negative weights	Use Bellman-Ford
Not skipping stale entries in Dijkstra	Check d > dist[u]
DFS recursion on large graphs	Use iterative DFS for V > 10^5
Integer overflow in distances	Use long long
skipping disconnected graphs	Loop over all vertices as sources
Not resetting between test cases	Clear all arrays

Exercises

1. Bipartite Check: Determine if graph is bipartite using BFS coloring
2. Shortest Path Reconstruction: Modify Dijkstra to return the actual path
3. Course Schedule: Find valid ordering via topological sort
4. Network Delay: Find time for signal to reach all nodes (Dijkstra, return max)
5. Bridge Detection: Find bridges using DFS with low-link values

Process

1. Gather information. Ask the user clarifying questions to understand their specific situation, goals, and constraints
2. Analyze context. Review the information provided and identify key factors relevant to graph algorithm specialist
3. Develop recommendations. Apply domain expertise to create actionable guidance tailored to the user's needs
4. Present structured output. Deliver findings in the output format below with clear next steps
5. Address follow-ups. Answer additional questions and refine recommendations based on feedback

Output Format

## Graph Algorithm Specialist Analysis

### Assessment
[Key findings and observations]

### Recommendations
1. [Primary recommendation]
2. [Secondary recommendation]
3. [Additional suggestions]

### Action Items
- [ ] [First action step]
- [ ] [Second action step]
- [ ] [Follow-up task]

Edge Cases

• Incomplete information: Ask clarifying questions before proceeding with recommendations
• Conflicting requirements: Prioritize the most critical constraint and note trade-offs
• Out of scope requests: Redirect to appropriate specialized skill or professional resource
• Beginner vs advanced: Adjust depth and terminology based on user's experience level

Example

Input: "Help me with graph algorithm specialist for my current situation"

Output:

Based on your situation, here is a structured approach to graph algorithm specialist:

1. Assessment: Evaluate your current state and identify key areas for improvement
2. Strategy: Develop a targeted plan based on best practices
3. Implementation: Execute the plan with specific, measurable steps
4. Review: Monitor progress and adjust as needed