Search the docs, videos, blog, apps, teams, skills and release notes.
At a glance
What it is
Guides graph algorithm mastery including BFS, DFS, shortest paths, minimum spanning trees, topological sort, and cycle detection with implementation patterns.
A skill is a written procedure a bot loads when a job calls for it. This one is a single file, SKILL.md, and the whole file is on this page.
The whole file, exactly as it downloads. Read it before you rely on it.
SKILL.md
505 lines · 2,062 words
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.
Use this skill when:
User asks about graph algorithm specialist techniques or best practices
Guides graph algorithm mastery including BFS, DFS, shortest paths, minimum spanning trees, topological sort, and cycle detection with implementation patterns.
Nothing. It ships with Murage, which is open source. Your bots run on the AI plan you already have.
Yes. Open it in Settings → Skills to read, edit or duplicate it. Skill Guard scans it again after every edit.
Download the app, connect the AI you already pay for, and tell your Chief of Staff what needs doing. Plan on about ten minutes from install to a working team.
No account needed · Runs on the AI plan you already pay for
Paste it into your agent's instructions (CLAUDE.md, AGENTS.md or a custom GPT), or add it to a bot in Murage.
Ask Ember for the bot, then switch the skill on in its settings.
Step 1
Send your Chief of Staff this message. It proposes the bot and its role first, and creates it when you say go.
Send this to Ember
“Create a bot that uses the Graph Algorithm Specialist skill, and show me the plan first.”
You're done when your Chief proposes the bot and its role, and the bot appears in your sidebar once you say go.
Step 2
You're done when you see the bot’s skills and the library.
Step 3
You're done when the skill shows as on for that bot.
Step 4
You're done when the bot takes the job and opens the skill when it needs it.
Prefer to do it yourself? Choose + in the sidebar, then New Bot.Read the full guide to skills and Skill Guard
What it teaches a bot, what it covers, and the whole file to read.
The principle
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.
What it covers
When to Use
Graph Representation
Breadth-First Search (BFS)
Depth-First Search (DFS)
Shortest Path Algorithms
Minimum Spanning Tree
Topological Sort
Cycle Detection
Strongly Connected Components (Kosaraju)
Common Pitfalls
Exercises
Process
Output Format
Edge Cases
Example
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
// 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 | 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 |
// 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;
}// 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;
}// 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;
}// 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);
}
}// 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];
}// 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;
}// 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;
}// 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};
}// 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 | 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 |
// 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 = 0;
int edgeCount = 0;
for (auto [w, u, v] : edges) {
if (uf.unite(u, v)) {
mstWeight += w;
if (++edgeCount == n - 1) break;
}
}
return mstWeight;
}// 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;
}// 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;
}// 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;
}// 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;
}// 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;
}// 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 - 1; i >= 0; i--) {
int u = order[i];
if (!visited[u]) { sccs.push_back({}); dfs2(u, sccs.back()); }
}
return sccs;
}| 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 |
Bipartite Check: Determine if graph is bipartite using BFS coloring
Shortest Path Reconstruction: Modify Dijkstra to return the actual path
Course Schedule: Find valid ordering via topological sort
Network Delay: Find time for signal to reach all nodes (Dijkstra, return max)
Bridge Detection: Find bridges using DFS with low-link values
Gather information. Ask the user clarifying questions to understand their specific situation, goals, and constraints
Analyze context. Review the information provided and identify key factors relevant to graph algorithm specialist
Develop recommendations. Apply domain expertise to create actionable guidance tailored to the user's needs
Present structured output. Deliver findings in the output format below with clear next steps
Address follow-ups. Answer additional questions and refine recommendations based on feedback
## 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]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
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:
Assessment: Evaluate your current state and identify key areas for improvement
Strategy: Develop a targeted plan based on best practices
Implementation: Execute the plan with specific, measurable steps
Review: Monitor progress and adjust as needed
SKILL.md
505 lines · 2,062 words
The text of SKILL.md is shown as it downloads, under the Apache-2.0 license, by Ferrox Labs. The license is the one in the file's own frontmatter.
Your new bot
Graph Algorithm Specialist bot
Waiting in your sidebar once you say go.
No account needed · Runs on the AI plan you already pay for