ส่วนประกอบที่เชื่อมต่อในรายการเชื่อมโยง (Linked List Components) ใน C++

ได้รับ linked list และเซต G (subset ของค่าใน list) หาจำนวน connected components ใน G โดยสองค่าเชื่อมต่อกันถ้าอยู่ติดกันใน linked list

ตัวอย่าง

Input − list=[0,1,2,3], G=[0,1,3] Output − 2

คำอธิบาย − 0-1 ติดกันเป็น component หนึ่ง, 3 อยู่คนเดียวอีก component → รวม 2

แนวทางการแก้ปัญหา

• ใส่ค่า G ลง set เพื่อ O(1) lookup
• เดิน linked list: ถ้าค่าอยู่ใน G และค่าก่อนหน้าไม่อยู่ใน G (หรือเป็นตัวแรก) → เริ่ม component ใหม่ (+1)
• ใช้ flag บอกว่ากำลังอยู่ใน component หรือไม่

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    int numComponents(ListNode* head, vector& G) {
        unordered_set s(G.begin(), G.end());
        int ans = 0;
        bool inComponent = false;
        while (head) {
            if (s.count(head->val)) {
                if (!inComponent) ans++;
                inComponent = true;
            } else {
                inComponent = false;
            }
            head = head->next;
        }
        return ans;
    }
};

int main() {
    ListNode* head = new ListNode(0);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    vector G = {0, 1, 3};
    Solution ob;
    cout << ob.numComponents(head, G); // 2
    return 0;
}

ผลลัพธ์

2