मान लीजिए हमने एक सिर दिया है; यह एक लिंक की गई सूची का प्रमुख नोड है जिसमें अद्वितीय पूर्णांक मान होते हैं। अब हमें सूची G भी दी गई है, जो लिंक की गई सूची में मानों का एक उपसमुच्चय है। हमें G में जुड़े हुए घटकों की संख्या ज्ञात करनी है, जहां दो मान जुड़े हुए हैं यदि वे लिंक की गई सूची में लगातार दिखाई देते हैं। तो अगर सूची [0,1,2,3] और जी =[0,1,3] की तरह है, तो आउटपुट 2 होगा, क्योंकि 0 और 1 जुड़े हुए हैं, इसलिए दो सूचियां हैं [0,1] और [3]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ret :=0, एक सेट बनाएं, और G के सभी तत्वों को s में डालें
- झंडा :=झूठा
- जबकि सिर खाली नहीं है
- x :=शीर्ष का मान
- यदि s में x है, तो
- अगर फ़्लैग गलत है, तो रिट को 1 से बढ़ाएँ
- झंडा :=सच
- अन्यथा ध्वज सेट करें:=झूठा
- सिर:=सिर के आगे
- रिटर्न रिटर्न
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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