C++-এ লিংকড লিস্ট কম্পোনেন্টস গণনা

মান করুন আমাদের একটি head দেওয়া আছে; এটি একটি লিংকড লিস্টের হেড নোড যাতে ইউনিক পূর্ণসংখ্যা মান রয়েছে। এছাড়া আমাদের একটি লিস্ট G দেওয়া আছে, যা লিংকড লিস্টের মানগুলির একটি সাবসেট। আমাদের G-এ কানেক্টেড কম্পোনেন্টের সংখ্যা বের করতে হবে, যেখানে দুটি মান কানেক্টেড বলা হবে যদি সেগুলো লিংকড লিস্টে একসাথে আসে।

যদি লিস্ট হয় [0,1,2,3] এবং G = [0,1,3], তবে আউটপুট হবে ২, কারণ 0 এবং 1 কানেক্টেড, তাই দুটি লিস্ট [0,1] এবং [3]।

এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −

ret := 0, একটি সেট s তৈরি করুন, এবং G-এর সব এলিমেন্ট s-এ ইনসার্ট করুন
flag := false
head null না হওয়া পর্যন্ত
- x := head-এর মান
- যদি s-এ x থাকে, তবে
  - যদি flag false হয়, ret 1 বৃদ্ধি করুন
  - flag := true
- অন্যথায় flag := false সেট করুন
- head := head->next
ret ফেরত দিন

উদাহরণ কোড

#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]