C++代码段错误排查请求：机场连接问题实现故障分析

Hey, let's figure out why your code is crashing with a segmentation fault and get it fixed. I've gone through your code and spotted several key issues that are causing the problem:

1. Iterator Invalidity When Erasing from checked #

Your loop to remove the current airport from checked has a critical flaw: when you call checked.erase(it1), the iterator it1 becomes invalid. Continuing to increment this invalid iterator leads to undefined behavior (which often manifests as a segfault).

Fix:
Use the return value of erase (which gives you a valid iterator to the next element) to update your loop variable:

for (vector<string>::iterator it1 = checked.begin(); it1 != checked.end(); ) {
    if (*it1 == x) {
        it1 = checked.erase(it1); // Update iterator to avoid invalidation
    } else {
        ++it1;
    }
}

2. Infinite Recursion from Cycles in Routes #

Your recursive check_routes function doesn't track visited nodes. When there's a cycle in your routes (like SIN → CDG → SIN), the function will recurse infinitely until the stack overflows, causing a segfault.

Fix:
Add an unordered_set to track visited nodes during each traversal, so you don't reprocess the same node:

void check_routes(string x, unordered_set<string>& visited) {
    // Stop if we've already visited this node to break cycles
    if (visited.count(x)) return;
    visited.insert(x);

    // ... existing erase logic ...

    // Use equal_range to efficiently get all routes starting from x
    auto route_range = routes.equal_range(x);
    for (auto it = route_range.first; it != route_range.second; ++it) {
        check_routes(it->second, visited);
    }
}

3. Broken Initialization of ports and checked #

You initialized ports with 17 empty strings first, then pushed 17 actual airport names—resulting in a ports vector with 34 elements (17 empty, 17 valid). checked inherits this mess, and your main loop tries to access checked[i] even when i exceeds the current size of checked (since elements are erased over time), leading to out-of-bounds access.

Fix:
Initialize ports directly with your airport list, then copy it to checked:

vector<string> ports = {
    "BUD", "BGI", "DEL", "DOH", "DSM", "EWR", "EYW",
    "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", // Fixed typo: BSAN → SAN
    "SFO", "SIN", "TLV"
};
vector<string> checked = ports; // Properly initialize checked with valid airports

Also, note you had a typo in your routes: DMS → ORD should be DSM → ORD (matching the airport name in ports).

4. Flawed Main Loop Logic #

Your main loop uses a fixed index i that increments regardless of checked's changing size. This will quickly lead to accessing indices beyond the vector's bounds.

Fix:
Instead, loop while checked isn't empty, and always pick the first element to start a new traversal:

int ans = 0;
while (!checked.empty()) {
    string start = checked[0];
    unordered_set<string> visited;
    check_routes(start, visited);
    ans++;
}

Full Fixed Code #

Putting all these fixes together, here's the working version of your code:

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

vector<string> ports = {
    "BUD", "BGI", "DEL", "DOH", "DSM", "EWR", "EYW",
    "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN",
    "SFO", "SIN", "TLV"
};
vector<string> checked = ports; 
multimap<string, string> routes; 

void check_routes(string x, unordered_set<string>& visited) {
    if (visited.count(x)) return;
    visited.insert(x);

    // Remove current airport from checked
    for (vector<string>::iterator it1 = checked.begin(); it1 != checked.end(); ) {
        if (*it1 == x) {
            it1 = checked.erase(it1);
        } else {
            ++it1;
        }
    }

    // Traverse all outgoing routes
    auto route_range = routes.equal_range(x);
    for (auto it = route_range.first; it != route_range.second; ++it) {
        check_routes(it->second, visited);
    }
}

int main () { 
    // Fixed typo: DMS → DSM
    routes.insert(make_pair("DSM", "ORD")); 
    routes.insert(make_pair("ORD", "BGI")); 
    routes.insert(make_pair("BGI", "LGA")); 
    routes.insert(make_pair("SIN", "CDG")); 
    routes.insert(make_pair("CDG", "SIN")); 
    routes.insert(make_pair("CDG", "BUD")); 
    routes.insert(make_pair("DEL", "DOH")); 
    routes.insert(make_pair("DEL", "CDG")); 
    routes.insert(make_pair("TLV", "DEL")); 
    routes.insert(make_pair("EWR", "HND")); 
    routes.insert(make_pair("HND", "ICN")); 
    routes.insert(make_pair("HND", "JFK")); 
    routes.insert(make_pair("ICN", "JFK")); 
    routes.insert(make_pair("JFK", "LGA")); 
    routes.insert(make_pair("EYW", "LHR")); 
    routes.insert(make_pair("LHR", "SFO")); 
    routes.insert(make_pair("SFO", "SAN")); 
    routes.insert(make_pair("SFO", "DSM")); 
    routes.insert(make_pair("SAN", "EYW")); 

    int ans = 0;
    while (!checked.empty()) {
        string start = checked[0];
        unordered_set<string> visited;
        check_routes(start, visited);
        ans++;
    }

    cout << ans << endl; 
    return 0; 
}

内容的提问来源于stack exchange，提问作者user13504846