Cycle Detection and Connectivity

Union-Find, DFS/BFS, and topological sorting can detect cycles and verify graph connectivity in $O(n + m)$ time. Topological sorting also identifies cycles in directed graphs.

Problem: Acyclic Directed Graph Check

Description: Given a directed graph with $N$ nodes and $M$ edges where each edge $(a_i, b_i)$ connects node $a_i$ to $b_i$, determine if the graph contains no cycles. Constraints: $2 \leq N, M \leq 100$.

Solution: Perform topological sorting. If the sorted sequence contains all nodes, the graph is acyclic.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void solve() {
    int node_count, edge_count;
    cin >> node_count >> edge_count;
    vector<vector<int>> graph(node_count + 1);
    vector<int> in_degree(node_count + 1, 0);
    
    for (int i = 0; i < edge_count; i++) {
        int src, dest;
        cin >> src >> dest;
        graph[src].push_back(dest);
        in_degree[dest]++;
    }
    
    queue<int> q;
    for (int i = 1; i <= node_count; i++) {
        if (in_degree[i] == 0) q.push(i);
    }
    
    int visited_nodes = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        visited_nodes++;
        for (int neighbor : graph[cur]) {
            if (--in_degree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    
    cout << (visited_nodes == node_count ? "Acyclic" : "Cyclic") << endl;
}

Problem: Tree Verification

Description: Determine if a directed graph is a tree. A tree has exactly one root (in-degree 0) and all other nodes have in-degree 1, with no cycles.

Solution: Combine union-find for cycle detection and in-degree validation.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;

const int MAX_NODES = 200005;
int parent[MAX_NODES];

int find_root(int x) {
    return (parent[x] == x) ? x : parent[x] = find_root(parent[x]);
}

void solve() {
    int case_num = 0;
    int src, dest;
    vector<pair<int, int>> edges;
    set<int> unique_nodes;
    
    while (cin >> src >> dest) {
        if (src == -1 && dest == -1) break;
        if (src == 0 && dest == 0) {
            case_num++;
            vector<int> node_list(unique_nodes.begin(), unique_nodes.end());
            sort(node_list.begin(), node_list.end());
            node_list.erase(unique(node_list.begin(), node_list.end()), node_list.end());
            
            int total_nodes = node_list.size();
            int total_edges = edges.size();
            for (int i = 0; i <= total_nodes; i++) parent[i] = i;
            
            vector<vector<int>> adj(total_nodes + 1);
            vector<int> in_degree(total_nodes + 1, 0);
            bool valid = true;
            
            for (auto& e : edges) {
                int u_idx = lower_bound(node_list.begin(), node_list.end(), e.first) - node_list.begin() + 1;
                int v_idx = lower_bound(node_list.begin(), node_list.end(), e.second) - node_list.begin() + 1;
                adj[u_idx].push_back(v_idx);
                in_degree[v_idx]++;
                
                int root_u = find_root(u_idx);
                int root_v = find_root(v_idx);
                if (root_u == root_v) valid = false;
                parent[root_u] = root_v;
            }
            
            int components = 0;
            for (int i = 1; i <= total_nodes; i++) {
                if (find_root(i) == i) components++;
            }
            valid = valid && (components == 1);
            
            int root_count = 0, mid_count = 0;
            for (int i = 1; i <= total_nodes; i++) {
                if (in_degree[i] == 0) root_count++;
                if (in_degree[i] == 1) mid_count++;
            }
            valid = valid && (root_count == 1) && (mid_count == total_nodes - 1);
            
            cout << "Case " << case_num << " is " << (valid ? "" : "not ") << "a tree.\n";
            edges.clear();
            unique_nodes.clear();
        } else {
            edges.push_back({src, dest});
            unique_nodes.insert(src);
            unique_nodes.insert(dest);
        }
    }
}

Cycle Enumeration

For directed graphs, the residual graph after topological sorting reveals cycles. Undirected graph cycle enumeration requires more advanced techniques.

Minimum and Maximum Cycle Problems

Unweighted Maximum Cycle

Perform DFS while tracking node depths. When revisiting a node, calculate cycle length as current depth minus ancestor depth plus one.

Problem: Largest Cycle in Undirected Graph Solution:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAX_VERTICES = 200005;
vector<int> adj_list[MAX_VERTICES];
int depth[MAX_VERTICES];
int max_cycle_size;

void dfs(int cur, int prev) {
    for (int neighbor : adj_list[cur]) {
        if (neighbor == prev) continue;
        if (depth[neighbor] == -1) {
            depth[neighbor] = depth[cur] + 1;
            dfs(neighbor, cur);
        } else {
            max_cycle_size = max(max_cycle_size, depth[cur] - depth[neighbor] + 1);
        }
    }
}

void solve() {
    int vertex_count, edge_count;
    cin >> vertex_count >> edge_count;
    for (int i = 1; i <= vertex_count; i++) {
        adj_list[i].clear();
        depth[i] = -1;
    }
    
    for (int i = 0; i < edge_count; i++) {
        int u, v;
        cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    
    depth[1] = 0;
    max_cycle_size = 0;
    dfs(1, -1);
    cout << max_cycle_size << endl;
}

General Minimum Cycle

Dijkstra-Based Approach

For each edge $(u, v, w)$, temporarily remove it and compute shortest path $d(u,v)$. Minimum cycle is $\min(d(u,v) + w)$ over all edges.

Problem: Minimum Cost Cycle Solution:

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

typedef pair<int, int> pii;
const int INF = INT_MAX;

struct Edge {
    int target, weight, next;
};

vector<Edge> edge_array;
vector<int> head;
int edge_counter;

void add_edge(int src, int dst, int wt) {
    edge_array.push_back({dst, wt, head[src]});
    head[src] = edge_counter++;
}

int dijkstra(int start, int end, int skip_src, int skip_dst) {
    vector<int> dist(head.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int cur_dist = pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();
        
        if (cur_dist != dist[cur_node]) continue;
        if (cur_node == end) return cur_dist;
        
        for (int idx = head[cur_node]; idx != -1; idx = edge_array[idx].next) {
            int nxt = edge_array[idx].target;
            int wgt = edge_array[idx].weight;
            if ((cur_node == skip_src && nxt == skip_dst) || 
                (cur_node == skip_dst && nxt == skip_src)) continue;
            
            if (dist[cur_node] + wgt < dist[nxt]) {
                dist[nxt] = dist[cur_node] + wgt;
                pq.push({dist[nxt], nxt});
            }
        }
    }
    return INF;
}

void solve() {
    int edge_count;
    cin >> edge_count;
    map<pair<int, int>, int> coord_map;
    vector<tuple<int, int, int>> edges;
    int node_id = 0;
    
    for (int i = 0; i < edge_count; i++) {
        int x1, y1, x2, y2, wt;
        cin >> x1 >> y1 >> x2 >> y2 >> wt;
        auto key1 = make_pair(x1, y1);
        auto key2 = make_pair(x2, y2);
        if (!coord_map.count(key1)) coord_map[key1] = node_id++;
        if (!coord_map.count(key2)) coord_map[key2] = node_id++;
        edges.push_back({coord_map[key1], coord_map[key2], wt});
    }
    
    head.assign(node_id + 1, -1);
    edge_counter = 0;
    edge_array.clear();
    
    for (auto& e : edges) {
        int u = get<0>(e), v = get<1>(e), w = get<2>(e);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    
    int min_cycle = INF;
    for (auto& e : edges) {
        int u = get<0>(e), v = get<1>(e), w = get<2>(e);
        int path_len = dijkstra(u, v, u, v);
        if (path_len != INF) min_cycle = min(min_cycle, path_len + w);
    }
    
    cout << (min_cycle == INF ? 0 : min_cycle) << endl;
}

Floyd-Based Approach

During Floyd-Warshall execution, for each intermediate node $k$, update minimum cycle using distances between nodes $i,j < k$ and edges $(i,k)$, $(k,j)$.

Problem: Minimum Cost Cycle in Undirected Graph Solution:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAX_SIZE = 105;
const int INF = INT_MAX;

void solve() {
    int vertex_count, edge_count;
    while (cin >> vertex_count >> edge_count) {
        vector<vector<int>> graph(vertex_count + 1, vector<int>(vertex_count + 1, INF));
        vector<vector<int>> dist(vertex_count + 1, vector<int>(vertex_count + 1, INF));
        
        for (int i = 1; i <= vertex_count; i++) {
            graph[i][i] = 0;
        }
        
        for (int i = 0; i < edge_count; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u][v] = graph[v][u] = min(graph[u][v], w);
        }
        
        for (int i = 1; i <= vertex_count; i++) {
            for (int j = 1; j <= vertex_count; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        int min_cycle = INF;
        for (int k = 1; k <= vertex_count; k++) {
            for (int i = 1; i < k; i++) {
                for (int j = i + 1; j < k; j++) {
                    if (dist[i][j] != INF && graph[i][k] != INF && graph[k][j] != INF) {
                        min_cycle = min(min_cycle, dist[i][j] + graph[i][k] + graph[k][j]);
                    }
                }
            }
            for (int i = 1; i <= vertex_count; i++) {
                for (int j = 1; j <= vertex_count; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        if (min_cycle != INF) cout << min_cycle << endl;
        else cout << "No cycle found" << endl;
    }
}

Positive and Negative Cycles

Detect negative cycles using Bellman-Ford: after $|V|-1$ relaxation passes, if any edge can still relax, a negative cycle exists.

Problem: Negative Cycle Detection Solution:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = LLONG_MAX;

void solve() {
    int vertex_count, edge_count;
    cin >> vertex_count >> edge_count;
    vector<vector<int>> edges;
    
    for (int i = 0; i < edge_count; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    
    vector<ll> distance(vertex_count + 1, INF);
    distance[1] = 0;
    
    for (int i = 1; i < vertex_count; i++) {
        for (auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (distance[u] != INF && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
            }
        }
    }
    
    vector<bool> in_cycle(vertex_count + 1, false);
    for (auto& e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (distance[u] != INF && distance[u] + w < distance[v]) {
            in_cycle[v] = true;
        }
    }
    
    bool found = false;
    for (int i = 1; i <= vertex_count; i++) {
        if (in_cycle[i]) {
            found = true;
            break;
        }
    }
    
    cout << (found ? "Negative cycle detected" : "No negative cycle") << endl;
}

Longest Path in Directed Acyclic Graphs

Transform to shortest path by negating weights. Compute using topological order.

Problem: Longest Path in DAG Solution:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = LLONG_MAX;

void solve() {
    int vertex_count, edge_count;
    cin >> vertex_count >> edge_count;
    vector<vector<pair<int, int>>> graph(vertex_count + 1);
    vector<int> in_degree(vertex_count + 1, 0);
    
    for (int i = 0; i < edge_count; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, -w}); // Negate weights
        in_degree[v]++;
    }
    
    queue<int> q;
    vector<int> topo_order;
    for (int i = 1; i <= vertex_count; i++) {
        if (in_degree[i] == 0) q.push(i);
    }
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        topo_order.push_back(cur);
        for (auto& neighbor : graph[cur]) {
            in_degree[neighbor.first]--;
            if (in_degree[neighbor.first] == 0) {
                q.push(neighbor.first);
            }
        }
    }
    
    vector<ll> dp(vertex_count + 1, INF);
    dp[1] = 0;
    for (int node : topo_order) {
        if (dp[node] == INF) continue;
        for (auto& edge : graph[node]) {
            int nxt = edge.first;
            int wgt = edge.second;
            if (dp[node] + wgt < dp[nxt]) {
                dp[nxt] = dp[node] + wgt;
            }
        }
    }
    
    if (dp[vertex_count] == INF) cout << -1 << endl;
    else cout << -dp[vertex_count] << endl; // Revert negation
}

Longest Path in General Graphs

Use Bellman-Ford on negated weights. Detect negative cycles affecting the destination.

Problem: Longest Path with Possible Infinite Value Solution:

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;

typedef long long ll;
const ll INF = LLONG_MAX;

void solve() {
    int vertex_count, edge_count;
    cin >> vertex_count >> edge_count;
    vector<vector<int>> edges(edge_count + 1, vector<int>(3));
    
    for (int i = 1; i <= edge_count; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    
    vector<ll> dist(vertex_count + 1, INF);
    dist[1] = 0;
    
    for (int i = 1; i <= vertex_count; i++) {
        for (int j = 1; j <= edge_count; j++) {
            int u = edges[j][0], v = edges[j][1];
            ll w = -edges[j][2]; // Negate for longest path
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    vector<bool> in_cycle(vertex_count + 1, false);
    vector<bool> reachable(vertex_count + 1, false);
    for (int j = 1; j <= edge_count; j++) {
        int u = edges[j][0], v = edges[j][1];
        ll w = -edges[j][2];
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            in_cycle[v] = true;
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= vertex_count; i++) {
        if (in_cycle[i]) {
            q.push(i);
            reachable[i] = true;
        }
    }
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int j = 1; j <= edge_count; j++) {
            if (edges[j][0] == cur && !reachable[edges[j][1]]) {
                reachable[edges[j][1]] = true;
                q.push(edges[j][1]);
            }
        }
    }
    
    if (reachable[vertex_count]) cout << "Infinity" << endl;
    else if (dist[vertex_count] == INF) cout << "Unreachable" << endl;
    else cout << -dist[vertex_count] << endl; // Revert negation
}