#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
#include <string>

/* Interface provided by the system — already implemented */
class HtmlParser {
public:
    std::vector<std::string> getUrls(const std::string& url);
};

/* Single-threaded Web Crawler without domain filtering */
class WebCrawlerSimple {
public:
    std::vector<std::string> crawl(const std::string& startUrl, HtmlParser& parser) {
        std::queue<std::string> q;               // BFS queue
        std::unordered_set<std::string> visited; // Set of visited URLs

        q.push(startUrl);
        visited.insert(startUrl);

        while (!q.empty()) {
            std::string url = q.front();
            q.pop();

            // Fetch all linked URLs from current page
            std::vector<std::string> links = parser.getUrls(url);

            for (const std::string& link : links) {
                if (visited.find(link) == visited.end()) {
                    visited.insert(link);
                    q.push(link);
                }
            }
        }

        return std::vector<std::string>(visited.begin(), visited.end());
    }
};

🧠 Time & Space Complexity

Let N = number of unique reachable URLs

Let E = total number of hyperlinks across all visited pages

Metric Complexity
Time O(N + E)
Space O(N)

Below is the multithreaded solution

class Solution {
private:
    unordered_set<string> visited;    // shared ⇒ critical
    queue<string> q;                  // shared ⇒ critical
    vector<string> result;            // shared ⇒ critical
    mutex mtx;                        // guards the above
    condition_variable cv;            // signals workers
    atomic<int> inFlight{0};          // track running tasks
    bool done = false;                // signal termination

    void worker(HtmlParser& htmlParser) {
        while (true) {
            string url;

            // 🔒 Critical Section 1: Fetch work from queue
            {
                unique_lock<mutex> lock(mtx);
                cv.wait(lock, [&]() { return done || !q.empty(); });

                if (done && q.empty())
                    return;

                url = q.front();
                q.pop();
                ++inFlight;
            }

            // 🔓 Non-critical: Fetch URLs
            vector<string> neighbors = htmlParser.getUrls(url);

            // 🔒 Critical Section 2: Insert new URLs
            {
                lock_guard<mutex> lock(mtx);
                for (const string& next : neighbors) {
                    if (visited.insert(next).second) {
                        q.push(next);
                        result.push_back(next);
                        cv.notify_all(); // wake other threads
                    }
                }

                if (--inFlight == 0 && q.empty()) {
                    done = true;
                    cv.notify_all();
                }
            }
        }
    }

public:
    vector<string> crawl(string startUrl, HtmlParser& htmlParser) {
        {
            lock_guard<mutex> lock(mtx);
            visited.insert(startUrl);
            q.push(startUrl);
            result.push_back(startUrl);
            inFlight = 1;
        }

        vector<thread> pool;
        int numThreads = thread::hardware_concurrency() ? thread::hardware_concurrency() : 4;
        for (int i = 0; i < numThreads; ++i)
            pool.emplace_back([&]() { worker(htmlParser); });

        for (auto& t : pool)
            t.join();

        return result;
    }
};

🧠 Critical Sections & Why They're Needed

Critical Section Code Lines Why It's Critical
CS1: Work Fetch q.front(), q.pop(), ++inFlight Accessing queue and inFlight must be atomic to avoid race conditions when multiple threads are fetching work.
CS2: Inserting New URLs visited.insert(), q.push(), result.push_back(), --inFlight, done flag These modify shared state. We must guard against: <ul><li>Duplicates in visited</li><li>Concurrent push into queue</li><li>Incorrect inFlight value causing threads to wait forever or finish early</li></ul>
Startup Initial insert into visited, queue, and result Needed because the first task is shared seed state.
Shutdown Signal Check q.empty() and inFlight == 0 Coordinating global completion without race conditions.

✅ Summary

This version guarantees: