Các thành phần liên thông trong Linked List C++

Cho head của linked list giá trị unique và tập con G. Đếm số connected components trong G: hai giá trị liên thông nếu liền kề trong linked list.

Ví dụ

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

Giải thích - 0-1 liên thông thành component 1, 3 riêng thành component 2.

Phương pháp tiếp cận

• Đưa G vào set để tra O(1)
• Duyệt linked list, flag = false
• Nếu node.val trong set:
  • Nếu !flag: count++, flag=true
• Ngược lại: flag=false

Ví dụ code C++

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

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int data) { val = data; next = NULL; }
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* ptr = head;
        while (ptr->next) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

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

int main() {
    vector<int> v1 = {0,1,2,3};
    vector<int> v2 = {0,1,3};
    ListNode* h1 = make_list(v1);
    Solution ob;
    cout << ob.numComponents(h1, v2);
    return 0;
}

Kết quả

2