Approach
Breadth-first search
For Web Crawler Multithreaded, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 61 lines of C++ from the credited upstream file 1242.cpp.
- The implementation visibly relies on sequence storage, hash lookup, work queue.
- 4 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1/**2 * 3 * 4 * class HtmlParser {5 * public:6 * vector<string> getUrls(string url);7 * };8 */9 10class Solution {11 public:12 vector<string> crawl(string startUrl, HtmlParser htmlParser) {13 queue<string> q{{startUrl}};14 unordered_set<string> seen{{startUrl}};15 const string& hostname = getHostname(startUrl);16 const int nThreads = std::thread::hardware_concurrency();17 vector<thread> threads;18 std::mutex mtx;19 std::condition_variable cv;20 21 auto t = [&]() {22 while (true) {23 unique_lock<mutex> lock(mtx);24 cv.wait_for(lock, 30ms, [&]() { return q.size(); });25 if (q.empty())26 return;27 auto cur = q.front();28 q.pop();29 lock.unlock();30 const vector<string> urls = htmlParser.getUrls(cur);31 lock.lock();32 for (const string& url : urls) {33 if (seen.contains(url))34 continue;35 if (url.find(hostname) != string::npos) {36 q.push(url);37 seen.insert(url);38 }39 }40 lock.unlock();41 cv.notify_all();42 }43 };44 45 for (int i = 0; i < nThreads; ++i)46 threads.emplace_back(t);47 48 for (std::thread& t : threads)49 t.join();50 51 return {seen.begin(), seen.end()};52 }53 54 private:55 string getHostname(const string& url) {56 const int firstSlash = url.find_first_of('/');57 const int thirdSlash = url.find_first_of('/', firstSlash + 2);58 return url.substr(firstSlash + 2, thirdSlash - firstSlash - 2);59 }60};61