मान लीजिए हमें एक हेड दिया गया है; यह एक लिंक्ड लिस्ट का हेड नोड है जिसमें अद्वितीय पूर्णांक मान हैं। अब हमें सूची G भी दी गई है, जो लिंक्ड लिस्ट में मानों का एक सबसेट है। हमें G में कनेक्टेड कंपोनेंट्स की संख्या ढूंढनी है, जहां दो मान कनेक्टेड हैं यदि वे लिंक्ड लिस्ट में लगातार दिखाई देते हैं। तो यदि सूची [0,1,2,3] जैसी है और G = [0,1,3], तो आउटपुट 2 होगा, क्योंकि 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 का अगला
- 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]
आउटपुट
2