Depth-First Search on Adjacency-Matrix Graphs

void DFS(MGraph G, Vertex v, void (*visit)(Vertex)) {
    visit(v);
    Visited[v] = true;
    for (Vertex w = 0; w < G->Nv; ++w)
        if (G->G[v][w] && !Visited[w])
            DFS(G, w, visit);
}

Breadth-First Search on Adjacency-List Graphs

void BFS(LGraph G, Vertex s, void (*visit)(Vertex)) {
    Vertex queue[MaxVertexNum];
    int front = 0, rear = 0;

    queue[rear++] = s;
    Visited[s] = true;

    while (front < rear) {
        Vertex v = queue[front++];
        visit(v);

        for (PtrToAdjVNode p = G->G[v].FirstEdge; p; p = p->Next)
            if (!Visited[p->AdjV]) {
                queue[rear++] = p->AdjV;
                Visited[p->AdjV] = true;
            }
    }
}

Minimum-Cost Partial Highway Construction

Given a set of cities, some already connected by bidirectional roads, compute the minimum cost to ensure every city is reachable while only paying for roads that are not yet built.

/* Prim-like MST on a filtered graph */
int partial_MST(int n) {
    const int INF = 0x3f3f3f3f;
    int cost[105][105], dist[105], vis[105] = {0};
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cost[i][j] = INF;

    int m = n * (n - 1) / 2;
    while (m--) {
        int u, v, w, state;
        scanf("%d%d%d%d", &u, &v, &w, &state);
        cost[u][v] = cost[v][u] = state ? 0 : w;
    }

    for (int i = 1; i <= n; ++i) dist[i] = cost[1][i];
    dist[1] = vis[1] = 0;

    int total = 0;
    for (int step = 1; step < n; ++step) {
        int u = -1, minD = INF;
        for (int i = 1; i <= n; ++i)
            if (!vis[i] && dist[i] < minD) { minD = dist[i]; u = i; }

        if (u == -1) break;
        total += dist[u];
        vis[u] = 1;

        for (int v = 1; v <= n; ++v)
            if (!vis[v] && cost[u][v] < dist[v])
                dist[v] = cost[u][v];
    }
    return total;
}

Full Highway Construction – MST with Connectivity Check

int full_MST(int n, int m) {
    const int INF = 0x3f3f3f3f;
    int g[1005][1005], dist[1005], vis[1005] = {0};

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            g[i][j] = INF;

    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = w;
    }

    for (int i = 1; i <= n; ++i) dist[i] = g[1][i];
    dist[1] = vis[1] = 0;

    int sum = 0;
    for (int step = 1; step < n; ++step) {
        int u = 0;
        for (int i = 1; i <= n; ++i)
            if (!vis[i] && dist[i] < dist[u]) u = i;

        if (u == 0) { puts("Impossible"); return -1; }

        sum += dist[u];
        vis[u] = 1;

        for (int v = 1; v <= n; ++v)
            if (!vis[v] && g[u][v] < dist[v])
                dist[v] = g[u][v];
    }

    printf("%d\n", sum);
    return sum;
}

Emergency Rescue – Dijkstra with Path Counting

Find the number of shortest paths and the maximum rescue teams that can be gatherde along any shoretst route.

void dijkstra(int n, int src) {
    const int INF = 0x3f3f3f3f;
    int dist[505], teams[505], cnt[505], pre[505];
    bool vis[505] = {false};

    fill(dist, dist + n, INF);
    fill(cnt, cnt + n, 0);
    dist[src] = 0;
    cnt[src] = 1;
    teams[src] = p[src];

    for (int i = 0; i < n; ++i) {
        int u = -1, minD = INF;
        for (int j = 0; j < n; ++j)
            if (!vis[j] && dist[j] < minD) { minD = dist[j]; u = j; }

        if (u == -1) break;
        vis[u] = true;

        for (int v = 0; v < n; ++v) {
            if (!vis[v] && l[u][v] != INF) {
                if (dist[v] > dist[u] + l[u][v]) {
                    dist[v] = dist[u] + l[u][v];
                    cnt[v] = cnt[u];
                    teams[v] = teams[u] + p[v];
                    pre[v] = u;
                } else if (dist[v] == dist[u] + l[u][v]) {
                    cnt[v] += cnt[u];
                    if (teams[v] < teams[u] + p[v]) {
                        teams[v] = teams[u] + p[v];
                        pre[v] = u;
                    }
                }
            }
        }
    }
}

Dual-Criteria Shortest Path (Time vs Distance)

Given a city map with two weights per edge (travel time and distance), output both the fastest route and the shortest-distance route from a given source to destination. If the two routes coincide, print them once.

/* Dijkstra twice, then compare paths */
void dual_dijkstra(int N, int S, int D) {
    /* Time-based Dijkstra */
    fill(tDist, tDist + N, INF);
    fill(tPre, tPre + N, -1);
    tDist[S] = 0;
    ...
    /* Distance-based Dijkstra */
    fill(dDist, dDist + N, INF);
    fill(dPre, dPre + N, -1);
    dDist[S] = 0;
    ...
    /* Path reconstruction and comparison omitted for brevity */
}

Critical Path in AOE Network

Compute the earilest completion time and list all critical activities in an Activity-On-Edge (AOE) network.

void critical_path(int n, int m) {
    vector<int> topo;
    int in[101] = {0}, el[101] = {0}, la[101];
    fill(la, la + 101, INF);

    /* Topological sort */
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!in[i]) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto e : adj[u]) {
            int v = e.v, w = e.w;
            el[v] = max(el[v], el[u] + w);
            if (--in[v] == 0) q.push(v);
        }
    }

    int project_time = *max_element(el + 1, el + n + 1);
    for (int u : topo) la[u] = project_time;

    for (auto it = topo.rbegin(); it != topo.rend(); ++it) {
        int u = *it;
        for (auto e : adj[u]) {
            int v = e.v, w = e.w;
            la[u] = min(la[u], la[v] - w);
        }
    }

    /* Output critical edges */
    for (int u = 1; u <= n; ++u)
        for (auto e : adj[u])
            if (el[u] + e.w == la[e.v])
                printf("%d->%d\n", u, e.v);
}