ส่วนประกอบรายการที่เชื่อมโยงใน C ++

สมมุติว่าเราให้ศีรษะ นี่คือส่วนหัวของรายการที่เชื่อมโยงที่มีค่าจำนวนเต็มที่ไม่ซ้ำกัน ตอนนี้เรายังได้รับรายการ G ซึ่งเป็นชุดย่อยของค่าในรายการที่เชื่อมโยง เราต้องหาจำนวนองค์ประกอบที่เชื่อมต่อใน G โดยที่ค่าสองค่าจะเชื่อมต่อกันหากปรากฏติดต่อกันในรายการที่เชื่อมโยง ดังนั้นหากรายการเป็นเหมือน [0,1,2,3] และ G =[0,1,3] เอาต์พุตจะเป็น 2 เนื่องจาก 0 และ 1 เชื่อมต่อกัน ดังนั้นจึงมีสองรายการ [0,1] และ [3].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=0, สร้างเซต s และแทรกองค์ประกอบทั้งหมดของ G ลงใน s
• ธง :=เท็จ
• ในขณะที่หัวไม่เป็นโมฆะ
  • x :=ค่าหัว
  • ถ้า s มี x แล้ว
    • ถ้าแฟล็กเป็นเท็จ ให้เพิ่ม ret โดย 1
    • flag :=true
  • มิฉะนั้น ตั้งค่าสถานะ :=false
  • หัว :=ข้างหัว
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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 != NULL){
         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;
      for(int i = 0; i < G.size(); i++)s.insert(G[i]);
      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;
   }
};
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));
}

อินพุต

[0,1,2,3]
[0,1,3]

ผลลัพธ์

2