Code for subgraphs

Answers.md

2 Solutions for Subgraphs

Smart loop

Uses the vector visited.

Special optimization:

1. With the vector visited,
2. for (int i = 0; i<nodes; i++){
3. if (!visited[i]){do bfs and increment the counter by 1}

This avoids iterating through the whole visited vector every time. It only does so once.

// Based on Edwar's code
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long
#include <cmath>

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // ============== Taking input
    vector<vector<int>> adj_list;
    int N, M;
    cin >> N >> M;
    adj_list.resize(N);
    for (int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list[b].push_back(a);
    }
    
    // =============== Initialisation for bfs
    vector<bool> visited(N, false); // Visited tracker
    queue<int> to_explore;
    
    // =============== Program loop
    // 1. Picks an unvisited node
    // 2. Starts bfs with that node as source (eliminates a subgraph)
    // 3. Increments counter
    int counter = 0;
    // KEY! We do this, and not iterate through the whole visited every time
    //.  to find an unvisited node.
    for (int i = 0; i<N; i++){
        if (visited[i]){
            continue;
        } else {
            to_explore.push(i);
            visited[i] = true;
            counter++;
        }
        while (!to_explore.empty()){
            int exploring = to_explore.front();
            to_explore.pop();
            for (int visiting : adj_list[exploring]){
                if (!visited[visiting]){
                    visited[visiting] = true;
                    to_explore.push(visiting);
                }
            }
        }
    }
    
    // ========= Output
    cout << counter;
}

Unordered_set

Instead of using a vector, we use an unordered_set containing all nodes not visited yet.

This works as it now takes O(1) time to extract an unvisited node.

// Based on Huai Zhi's code
#include <bits/stdc++.h>
using namespace std;

#define int long long
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // ================ TAKE INPUT
    int N, E;
    cin >> N >> E;
    vector<vector<int>> nodes(N);

    for (int a = 0; a < E; a++) {
        int x, y;
        cin >> x >> y;
        nodes[x].push_back(y);
        nodes[y].push_back(x);
    }

    // ================ Set up our replacement for vector<bool> visited
    unordered_set<int> bb; // KEY!! bb will contain all nodes not visited yet.
    for (int i = 0; i < N; i++) {
        bb.insert(i); // mark all nodes as still unvisited
    }

    // ================ Actual program loop.
    // 1. Picks an unvisited node
    // 2. Runs bfs with that node as the source (eradicates a subgraph)
    // 3. Increment the subgraph counter
    int ans = 0;
    while (bb.size() > 0) { // While unvisited nodes exist,
        int new_bfs = *bb.begin(); // Select an unvisited node
        
        // Start bfs
        queue<int> toexplore;
        bb.erase(new_bfs); // Set new_bfs as the bfs source.
        toexplore.push(new_bfs);
        
        // Run the bfs
        while (!toexplore.empty()) {
            int exploring = toexplore.front();
            toexplore.pop();
            for (int visiting: nodes[exploring]) {
                if (bb.find(visiting) != bb.end()) {
                    bb.erase(visiting);
                    toexplore.push(visiting);
                }
            }
        }
        ans++; // Increase counter by 1
    }

    // ================ Answer
    cout << ans;

    return 0;
}