In this paper, we present a novel solution called Internet Footprint Investigation (IFI) for the rapid detection of network outages after a natural or man-made disaster. IFI is comprised of two components: 1) the Active Network Probing (ANP) module, which proactively probes the network infrastructure to detect geographic areas that may be disconnected; and 2) the Reactive Footprint Search (RFS) module, a reactive mechanism that improves the accuracy of the ANP results by incorporating the footprints of location-based social networks (LBSNs) established after a disaster occurs. Using Typhoon Morakot, which struck Taiwan in August 2009, as a case study, we implement the IFI system and evaluate its feasibility in a real-world scenario. We observe that the accuracy of existing IP geolocation services is unsatisfactory, and posit that localized IP geolocation services should be deployed and maintained all the times. Moreover, we demonstrate how existing LBSNs can be used to search for disaster victims in areas reported by ANP, and identify so-called "critical areas", which have no Internet activity, for priority inspection. The proposed IFI solution is simple and effective, and it can be deployed worldwide.