We are given head, the head node of a linked list containing unique integer values.
We are also given the list G, a subset of the values in the linked list.
Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.
Example 1:
Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:
Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note: 

If N is the length of the linked list given by head, 1 <= N <= 10000.
The value of each node in the linked list will be in the range [0, N - 1].
1 <= G.length <= 10000.
G is a subset of all values in the linked list.

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        

Solutions:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        s=set(G)
        prev_in=False
        c=0
        while head:
            if head.val in s:
                if not prev_in:
                    c+=1 
                prev_in=True
            else:           
                prev_in=False
            head=head.__next__
        return c


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        graph = set(G)
        result = 0
        while head:
            if head.val in graph and (head.__next__ == None or head.next.val not in graph):
                result += 1
            
            head = head.__next__
        return result
        
    def numComponents_standard(self, head: ListNode, G: List[int]) -> int:
        
        # construct the graph
        graph = collections.defaultdict(dict)
        
        for node in G:
            graph[node][node] = True
        
        while head:
            # have a edge
            if head.__next__ and head.val in graph and head.next.val in graph:
                graph[head.val][head.next.val] = True
                graph[head.next.val][head.val] = True
            head = head.__next__
            
        # Find connected components, by BFS
        result, queue, visited = 0, collections.deque(), set()
        
        for g in graph:
            if g not in visited:
                queue.append(g)
                result += 1
                while queue:
                    node = queue.pop()
                    visited.add(node)
                    neighbors = graph[node]
                    for nei in neighbors:
                        if nei not in visited:
                            queue.append(nei)
        return result
    
    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        d={}
        n=len(G)
        for i in range(0,n):
            d[G[i]]=i
        fa=[i for i in range(0,n)]
        rank=[1]*n
        def find(x):
            if fa[x]!=x:
                fa[x]=find(fa[x])
            return fa[x]
        def union(x,y):
            
            if x==y:
                return 
            else:
                i=fa[x]
                j=fa[y]
                if rank[i]<=rank[j]:
                    fa[i]=j
                else:
                    fa[j]=i
                if rank[i]==rank[j]:
                    rank[j]+=1
        p=head
        while(p and p.__next__):
            if p.val in d and p.next.val in d:
                
                union(d[p.val],d[p.next.val])
            p=p.__next__
        
        # merge res
        r=0
        rset=set()

        for i in range(0,n):
            tmp=find(i)
            if tmp not in rset:
                rset.add(tmp)
                r+=1
        return r
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        res = 0
        while head:
            if head.val in G:
                if not head.next:
                    res += 1
                elif head.next.val not in G:
                    res+=1
            head = head.next
        return res

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        count = 0
        while head:
            
            if head.val in G and (head.__next__ == None or head.next.val not in G):
                count += 1            
            head = head.__next__
        
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        x = []
        count=0
        while head:
            if head.val in G and (head.__next__ is None or head.next.val not in G):
                count+=1
            head =head.__next__
        return count
        
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        
        flag=0
        count=0
        temp=head
        while temp:
            if temp.val in G:
                flag=1
            else:
                if flag == 1:
                    count+=1
                    
                flag=0
                
            temp=temp.next
            
        if flag==1:
            count+=1
            
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        while head:
            if head.val in G:
                if not (head.next and head.next.val in G):
                    count += 1
            head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        while(head):
            if(head.val in G and (not head.next or head.next.val not in G)):
                count += 1
            head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0] * n
        
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.r[x] < self.r[y]:
            self.p[x] = y
            self.r[y] += self.r[x]            
        else:
            self.p[y] = x
            self.r[x] += self.r[y]

class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        dsu = DSU(max(G)+1)
        
        slow, fast = head, head.next
        while slow and fast:
            if slow.val in G and fast.val in G:
                dsu.union(slow.val, fast.val)
            slow, fast = slow.next, fast.next
        
        return len({dsu.find(x) for x in G})

class Solution:
    def numComponents(self, head: ListNode, g: List[int]) -> int:
        count = 0

        while head:
            if head.val in g and (head.next is None or head.next.val not in g):
                count += 1
            head = head.next
        return count

class Solution:
    def numComponents(self, head: ListNode, g: List[int]) -> int:
        count = 0

        while head:
            if head.val in g:
                if head.next and head.next.val in g:
                    head = head.next
                    continue
                count += 1
            head = head.next

        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        count = len(G)
        temp = head
        while(temp.next != None):
            
            if temp.val in G and temp.next.val in G:
                
                count -= 1
            
            temp = temp.next
        
        return count

from collections import defaultdict
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class UF:
    def __init__(self):
        self.p = {}
        self.r = defaultdict(lambda: 1)
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.r[x] > self.r[y]:
            self.p[y] = x
        elif self.r[x] < self.r[y]:
            self.p[x] = y
        else:
            self.p[x] = y
            self.r[y] += 1
    
    def find(self, x):
        if self.p.get(x, x) != x:
            self.p[x] = self.find(self.p.get(x,x))
        return self.p.get(x, x)

class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        uf = UF()
        # uf.union(head.val, head.next.val)
        # return 0 
        gSet = set(G)
        prev = head.val
        head = head.next
        # print(\"AB\")
        while head != None:
        # for i in range(1):
            # print
            curr = head.val
            if curr in gSet and prev in gSet:
                uf.union(curr, prev)
                # return 1
            head = head.next
            prev = curr
        # return 0  
        resSet = set()
        # print(G[1])
        # print(uf.p)
        # resSet.add(uf.find(i))
        # resSet.add(uf.find(G[1]))
        # return 10
        for i in G:
            # print(i)
            resSet.add(uf.find(i))
        # print(resSet, uf.p)
        return len(resSet)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        prev = None
        while head:
            if head.val in G and not prev in G:
                count += 1
            prev = head.val
            head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        temp = head
        while temp:
            if temp.val in G and (temp.__next__ == None or temp.next.val not in G):
                    count += 1
            temp = temp.__next__
        return count
                    
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        node=head
        while(node):
            temp=node
            if node.val in G and getattr(node.next,'val',None) not in G:
                count+=1
            node=node.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        while head:
            if head.val in G and (head.next==None or head.next.val not in G):
                count+=1
            head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        def dfs(head, i):
            if not head:
                return
            if head.val in G:
                G[head.val] = i
            dfs(head.next, i+1)
        G = collections.Counter(G)
        ans = 1
        dfs(head, 0)
        sortedValues = sorted(G.values())
        for i in range(1, len(sortedValues)):
            if sortedValues[i] != sortedValues[i-1]+1:
                ans += 1
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        # construct the graph
        graph = collections.defaultdict(dict)
        
        for node in G:
            graph[node][node] = True
        
        while head:
            # have a edge
            if head.__next__ and head.val in graph and head.next.val in graph:
                graph[head.val][head.next.val] = True
                graph[head.next.val][head.val] = True
            head = head.__next__
        print(graph)
        # Find connected components, by BFS
        result, queue, visited = 0, collections.deque(), set()
        
        for g in graph:
            if g not in visited:
                queue.append(g)
                result += 1
                while queue:
                    node = queue.pop()
                    visited.add(node)
                    neighbors = graph[node]
                    for nei in neighbors:
                        if nei not in visited:
                            queue.append(nei)
        return result
    
    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        GS = set(G)
        count = 0
        status = 0
        
        if not head or not G: return 0
        
        while head:
            if head.val in GS:
                status = 1
                GS.remove(head.val)
            else:
                if status ==1:
                    count +=1
                    status =0
            head = head.__next__
        if status ==1:
            count +=1
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        res = 0
        s = set(G)
        def func(head, path):
            nonlocal res
            if head:
                nonlocal s
                if head.val in s:
                    path.append(head.val)
                    s.remove(head.val)
                    func(head.next, path.copy())
                else:
                    if len(path):   res += 1
                    func(head.next, [])
            else:
                if len(path):   res += 1
        func(head, [])
        return res

from collections import defaultdict
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class UF:
    def __init__(self):
        self.p = {}
        self.r = defaultdict(lambda: 1)
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.r[x] > self.r[y]:
            self.p[y] = x
        elif self.r[x] < self.r[y]:
            self.p[x] = y
        else:
            self.p[x] = y
            self.r[y] += 1
    
    def find(self, x):
        if self.p.get(x, x) != x:
            self.p[x] = self.find(self.p.get(x,x))
        return self.p.get(x, x)

class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        uf = UF()
        # uf.union(head.val, head.next.val)
        # return 0 
        gSet = set(G)
        prev = head.val
        head = head.next
        # print(\"AB\")
        while head != None:
        # for i in range(1):
            # print
            curr = head.val
            if curr in gSet and prev in gSet:
                uf.union(curr, prev)
                # return 1
            head = head.next
            prev = curr
        # return 0  
        resSet = set()
        # print(G[1])
        # print(uf.p)
        # resSet.add(uf.find(i))
        # resSet.add(uf.find(G[1]))
        # return 10
        for i in G:
            # print(i)
            resSet.add(uf.find(i))
        print(resSet, uf.p)
        return len(resSet)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        newG = set(G)
        cnt = 0
        start = None
        while head != None:
            if head.val not in newG:
                if start != None:
                    start = None
                    cnt += 1
            else:
                start = 1
            head = head.__next__
        if start != None:
            cnt += 1
        return cnt
                


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, l: List[int]) -> int:
        l=set(l)
        n=len(l)
        temp=head
        while(temp and temp.__next__):
            if(temp.val in l and temp.next.val in l):
                n-=1
            temp=temp.__next__
        return n


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        res, s = 0, set(G)
        start = False
        while head:
            if head.val in s:
                if not start:
                    res += 1
                    start = True
            else:
                if start:
                    start = False
            head = head.next
        return res

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        ##################################################################
        # N.B Description is pure bullshit 
        # solution 1, iterate through 
        components = 0
        G = set(G) # convert to set 
        
        while head: # iterate through
            if head.val in  G and ( head.__next__ == None or head.next.val  not in  G):

                components += 1 
            head = head.__next__ 
            
        return components
        ##################################################################



# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        Gset = set(G)
        current = head
        ans = 0
        while current:
            if current.val in Gset:
                if current.next and current.next.val not in Gset or current.next is None:
                # if current.next and current.next.val not in Gset:
                    ans += 1
            current = current.next
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        G = set(G)
        temp = head
        isConnected = False
        connections = 0
        while temp != None:
            if temp.val in G:
                connections += 0 if isConnected else 1
                isConnected = True
            else:
                isConnected = False
            temp = temp.next
        return connections

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        ans = 0
        if not head:
            return ans
        G=set(G)
  
        if head.val in G:
            ans += 1
            prev_con = True
        else:
            prev_con = False
        
        node = head.__next__
        while node:
            if node.val in G:
                if not prev_con:
                    ans += 1
                    prev_con = True
            else:
                prev_con = False
            node = node.__next__
        return ans


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        Gset = set(G)
        cur = head
        ans = 0
        while cur:
            if (cur.val in Gset and getattr(cur.next, 'val', None) not in Gset):
                ans += 1
            cur = cur.next 
        
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        uniques = set(G)
        isConnected = False
        num = 0
        while head:
            if not isConnected and (head.val in uniques):
                isConnected = True
                num += 1
            if head.val not in uniques:
                isConnected = False
            head = head.__next__
        return num


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        c = 0
        els = {}
        check = False
        for el in G:
            els[el] = True
        while head != None:
            if head.val in els:
                if not check:
                    c += 1
                    check = True
            else:
                check = False
            head = head.__next__
        return c


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        setG = set(G)
        res = 0
        while head:
            if head.val in setG and (head.__next__ == None or head.next.val not in setG):
                res += 1
            head = head.__next__
        return res


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if not head or not G:
            return 0
        
        ht = {}
        for component in G:
            ht[component] = True
        if head.val in ht:
            total = 1
        else:
            total = 0
        prev = head
        while(head.next):
            head = head.next
            if head.val in ht and prev.val in ht :
                if total == 0:
                    total = 1
                continue
            elif head.val in ht:
                total += 1
            prev = head 
        return total

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if head == None:
            return 0
        if len(G) == 0:
            return 0
        
        resNum = 0
        pre = None
        GG = set(G)
        while head:
            if head.val in GG and resNum == 0:
                resNum += 1
            elif head.val in GG and pre not in GG:
                resNum += 1

            pre = head.val
            head = head.next
            
        return resNum

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        num_ccs = 0
        
        nodes = set(G)
        last_was_cc = False
        
        while head is not None:
            if head.val in nodes:
                if not last_was_cc:
                    num_ccs += 1
                last_was_cc = True
            else:
                last_was_cc = False
                
            head = head.next
            
        return num_ccs

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        Gset = set(G)
        current = head
        ans = 0
        while current:
            if current.val in Gset:
                if current.next and current.next.val not in Gset or current.next is None:
                    ans += 1
            current = current.next
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if not head or not G:
            return 0
        
        ht = {}
        for component in G:
            ht[component] = True
        if head.val in ht:
            total = 1
        else:
            total = 0
        prev = head
        while(head.next):
            head = head.next
            if head.val in ht and prev.val in ht :
                continue
            elif head.val in ht:
                total += 1
            prev = head 
        return total

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if head is None: return 0
        s = set(G)
        cur = head
        count = 0
        
        while cur:
            seen = set()
            if cur.val not in seen and cur.val in s:
                
                while cur and cur.val not in seen and cur.val in s:
                    seen.add(cur.val)
                    cur = cur.__next__ 
                count += 1
            else:
                cur = cur.__next__ 
        return count
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        temp = head
        inG = {}
        
        N = 1
        inG[temp.val] = None
        while(temp.__next__ != None):
            inG[temp.next.val] = None
            temp = temp.__next__
            N+=1
    
        for g in G:
            inG[g] = g
        
        
        temp = head
        while(temp.__next__ != None):
            if(inG[temp.next.val] != None and inG[temp.val] != None):
                # connect temp and temp.next in G list
                inG[temp.next.val] = inG[temp.val]
                
            temp = temp.__next__
            
        if(None not in set(inG.values())):
            return 1
        else:
            return len(set(inG.values())) - 1
            
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if not head or not G:
            return 0
        allCom = []
        com = []
        while head:
            
            while head and head.val in G:
                com.append(head.val)
                G.remove(head.val)
                head = head.__next__
            # constructed component?
            if com:
                allCom.append(com)
                com = []
            if head:
                head = head.__next__
            else:
                break
        return len(allCom)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, g: List[int]) -> int:
        g.sort()
        n = 0
        temp = head
        while temp != None:
            n += 1
            temp = temp.next
        a = [0]*n
        i = 0
        ans = 0
        while head and i < n:
            if head.val in g:
                a[i] = 1
            i += 1
            head = head.next
        for i in range(n):
            if a[i] == 1:
                if i == 0:
                    ans += 1
                elif a[i-1] == 0:
                    ans += 1
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        curr = head
        ccCount = 0
        inCC = False
        while curr is not None:
            if curr.val in G:
                if not inCC:
                    ccCount += 1
                G.remove(curr.val)
                inCC = True
            else:
                inCC = False
            curr = curr.next
        return ccCount

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        setG = set(G)
        output = 0
        while head:
            if head.val in setG:
                output += 1
                while head and head.val in G:
                    head = head.next
            else:
                head = head.next
        return output

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        normal_list = []
        while head:
            normal_list.append(head.val)
            head = head.next
            
        print(\"normal_list: \", normal_list)
        
        G.sort()
        print(\"G: \", G)
        
        groups = 0
        stack = []
        group_started = False
        
        # traverse normal_list
        while len(normal_list) > 0:
            a = normal_list.pop(0)
            if a in G:
                group_started = True
            else:
                if group_started == True:
                    groups += 1
                    group_started = False
        
        if group_started == True:
            groups += 1
        
        return groups
            
        
#         i = 0
#         while i < len(normal_list):
#             while i < len(normal_list) and normal_list[i] != G[i]:
#                 G.insert(i, \"\")
#                 i+=1
            
#             i+=1
            
#         print(\"G: \", G)
        
#         groups = 0
        
#         g = 0
#         groups_started = False
#         while g < len(G):
#             if G[g] != '':
#                 groups_started = True
#             else:
#                 if groups_started == True:
#                     groups += 1
#                     groups_started = False
#             g+=1
        
#         if groups_started == True:
#             groups +=1 # for the last one
        
#         print(\"groups: \", groups)
#         return groups
        
        
        

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        gset=set(G)
        count=0
        while head:
            if head.val in gset and (head.__next__ is None or head.next.val not in gset):
                count+=1
            head=head.__next__
        return count    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def binarySearch(self,val,G):
        start = 0
        end = len(G)-1
        while start <=end:
            mid = (start+end)//2
            if G[mid] == val:
                return True
            elif G[mid] > val:
                end=mid-1
            else:
                start = mid+1
        return False
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        G.sort()
        curr = head
        i = 0
        dict_clusters = {}
        while curr is not None:
            if i not in dict_clusters:
                dict_clusters[i] = []
            if self.binarySearch(curr.val,G):
                dict_clusters[i].append(curr.val)
            if curr.val not in G:
                i+=1
            curr = curr.__next__
        # print(dict_clusters)
        count = 0
        for i in dict_clusters:
            if len(dict_clusters[i])>0:
                count+=1
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        #s = set(G)
        
        prevIn = False
        while head:
            if head.val in G:
                if prevIn:
                    G.remove(head.val)
                else:
                    prevIn = True
            else:
                prevIn = False
            
            head = head.__next__
        
        return len(G)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        s=set(G)
        ctr=0
        currently_connected=False
        while head:
            if head.val in G:
                if not currently_connected:
                    ctr+=1
                    currently_connected=True
            else:
                currently_connected=False
            head=head.__next__
        return ctr


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        con = False
        while head:
            if head.val in G:
                if not con:
                    con = True
                    count += 1
            else:
                if con:
                    con = False
            head = head.__next__
        return count
                
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if not head or not G: return 0
        count = 0
        flag = 0
        while head:
            if head.val in G:
                flag = 1
            else:
                if flag:
                    count += 1
                    flag = 0
            head = head.next
        if flag: count += 1
            
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        initial_c = len(G)
        
        runner = head
        ans = []
        conn_ll = []
        while runner:
            if runner.val in G:
                conn_ll.append(runner.val)
            else:
                if conn_ll:
                    ans.append(conn_ll[:])
                    conn_ll = []
            runner = runner.next
            
        if conn_ll:
            ans.append(conn_ll)
        print(ans)

        return len(ans)

from collections import defaultdict


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if not head:
            return 0
        
        temp = head
        prev = None
        adj = defaultdict(list)
        
        while temp:
            adj[temp.val] += [prev.val if prev else None, temp.next.val if temp.next else None]
            prev = temp
            temp = temp.__next__
        
        exists = defaultdict(bool)
        for g in G:
            exists[g] = True    
        
        visited = defaultdict(bool)
            
        ans = 0
        for g in G:
            if not visited[g]:
                ans += 1
                queue = [g]
                while queue:
                    node = queue[0]
                    queue = queue[1:]
                    visited[node] = True
                    for j in adj[node]:
                        if j is not None and not visited[j] and j in G:
                            queue.append(j)
                            visited[j] = True
                
        return ans
            


from collections import defaultdict


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        if not head:
            return 0
        
        temp = head
        prev = None
        adj = defaultdict(list)
        
        while temp:
            adj[temp.val] += [prev.val if prev else None, temp.next.val if temp.next else None]
            prev = temp
            temp = temp.next
        
        \"\"\"exists = defaultdict(bool)
        for g in G:
            exists[g] = True    
        \"\"\"
        visited = defaultdict(bool)
            
        ans = 0
        for g in G:
            if not visited[g]:
                ans += 1
                queue = [g]
                while queue:
                    node = queue[0]
                    queue = queue[1:]
                    visited[node] = True
                    for j in adj[node]:
                        if j is not None and not visited[j] and j in G:
                            queue.append(j)
                            visited[j] = True
                
        return ans
            
            

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        ans = 0
        cnt = 0
        while head:
            if head.val in G:
                cnt = 1
            else:
                ans += cnt
                cnt = 0
            head = head.__next__

        return ans+cnt


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents_v1(self, head: ListNode, G: List[int]) -> int:
        
        # traverse list & count conn-comp
        count = 0               # keep track of number of comps
        new_comp = False        # flag if a new comp is in progress
        while head:
            
            # filter out elements not in G
            if head.val in G:
                # a new comp detected
                if not new_comp:
                    new_comp = True
                    count += 1
            else:
                # flag the current comp (if in progress) is done
                new_comp = False
                
            # try next element
            head = head.__next__
        
        return count
    
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        return self.numComponents_v1(head, G)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        connected_components = 0
        q = head
        G = set(G)
    
        
        while q is not None:
            if q.val in G:
                while q is not None and q.val in G:
                    q = q.__next__
                connected_components += 1
            if q is not None:
                q = q.__next__
                
        return connected_components
    
    
#             count = 0
#         p1, p2 = head, head
#         while p2:
#             if p1.val in G:
#                 p2 = p1.next
#                 p1 = p2
#                 if not p2 or p2.val not in G:
#                     count+=1
#             else:
#                 p1 = p2.next
#                 p2 = p1
#         return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        window = False
        connected = 0
        node = head 
        while node:
            if node.val in G:
                window = True
            else:
                if window:
                    connected += 1
                    window = False
            node = node.__next__
        if window:
            connected +=1
        return connected
                    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        curr_node = head
        value_in = False
        no = 0
        while curr_node:
            if value_in:
                if not curr_node.val in G:
                    no = no + 1
                    value_in = False
            else:
                if curr_node.val in G:
                    value_in = True
                
            curr_node = curr_node.next
        if value_in:
            no = no + 1
        return no

class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        tail = head
        components = 0
        connected = False
        while tail is not None:
            if tail.val in G:
                connected = True
            elif connected:
                components += 1
                connected = False
            tail = tail.next
        if connected:
            components += 1
            connected = False
        return components

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        res = 0
        flag = 0
        while head:
            if head.val in G:
                if flag == 0:
                    res += 1
                flag = 1
            else:
                flag = 0
            head = head.next
        return res

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        temp=0
        s=1
        while head:
            if head.val in G:
                temp+=1
            else:
                temp=0
                s=1
            head=head.next
            if temp>0 and s==1:
                s=0
                count+=1
        if temp>0 and s==1:
                s=0
                count+=1
            
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count =0 
        temp = head
        while temp:
            if temp.val not in G:
                temp = temp.__next__ 
                continue
            curr = temp.__next__
            while curr:
                if curr.val not in G:
                    curr = curr.__next__ 
                    break 
                else:
                    curr  = curr.__next__ 
            count +=1
            temp = curr 
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        cur = head
        con = 0
        ans = 0
        while cur:
            if cur.val not in G:
                if con != 0:
                    ans += 1
                con = 0
            else:
                con += 1
            cur = cur.next
        if con != 0:
            ans += 1
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        curr_node = head
        value_in = False
        no = 0
        while curr_node:
            if curr_node.val in G:
                value_in = True
            else:
                if value_in:
                    no = no + 1
                    value_in = False
            curr_node = curr_node.__next__
        if value_in:
            no = no + 1
        return no


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        cur = head
        cnt = 0
        flg = False
        while cur != None:
            if cur.val in G:
                if flg:
                    pass
                else:
                    flg=True
                    cnt+=1
            elif flg:
                flg=False
            cur = cur.__next__
        return cnt


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        ##################################################################
        # solution 1, iterate through 
        components = 0
        G_set = set(G) # convert to set 
        
        while head: # iterate through
            if head.val in  G_set and ( head.__next__ == None or head.next.val  not in  G_set):
                G_set.remove(head.val)

                components += 1 
            head = head.__next__ 
            
        return components
        ##################################################################



# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        cur = head
        cons = False
        while(cur):
            if cur.val in G:
                if not cons:
                    cons = True
                    count +=1
            else:
                cons = False
            cur = cur.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        connected_components = 0
        q = head
        
        while q is not None:
            if q.val in G:
                while q is not None and q.val in G:
                    q = q.__next__
                connected_components += 1
            if q is not None:
                q = q.__next__
                
        return connected_components
    
    
#             count = 0
#         p1, p2 = head, head
#         while p2:
#             if p1.val in G:
#                 p2 = p1.next
#                 p1 = p2
#                 if not p2 or p2.val not in G:
#                     count+=1
#             else:
#                 p1 = p2.next
#                 p2 = p1
#         return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        result = 0
        node = head
        tmp = []
        while node is not None:
            if node.val in G:
                tmp.append(node.val)
                node = node.next
            else:
                if tmp:
                    result += 1
                    tmp = [] 
                node = node.next
        if tmp:
            result += 1
        return result

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        val = False
        count = 0
        while head:
            if head.val in G:
                val = True
                
                while head and head.val in G:
                    head = head.__next__
                count += 1
            if head:
                head = head.__next__
            
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        curr = head
        components = 0
        
        in_component = False
        while curr != None:
            if curr.val in G:
                in_component = True
            elif in_component:
                components += 1
                in_component = False

            curr = curr.next
            
        if in_component:
            components += 1
            
        return components

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        comp = False
        count = 0
        while(head):
            if(head.val in G):
                if(not comp):
                    comp = True
            else:
                if(comp):
                    count += 1
                    comp = False
            
            head = head.next
            
        return count + 1 if comp else count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        while head:
            if head.val in G:
                while head and head.val in G:
                    head = head.next
                count += 1
                if not head:
                    break
            head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        res = [0]
        tmp_count = 0
        while head:
            if head.val not in G:
                res.append(tmp_count)
                tmp_count = 0
            else:
                tmp_count += 1
            
            head = head.__next__
        res.append(tmp_count)
        count = 0
        for i in res:
            if i !=0:
                count += 1
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, g: List[int]) -> int:
        g = set(g)
        n = 0
        temp = head
        while temp != None:
            n += 1
            temp = temp.next
        a = [0]*n
        i = 0
        ans = 0
        while head and i < n:
            if head.val in g:
                a[i] = 1
            i += 1
            head = head.next
        for i in range(n):
            if a[i] == 1:
                if i == 0:
                    ans += 1
                elif a[i-1] == 0:
                    ans += 1
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        while head:
            if head.val in G:                
                while head and head.val in G:
                    head = head.__next__
                count += 1
            if head:
                head = head.__next__
            
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        p=head
        while(p!=None):
            if p.val in G:
                count+=1
                q=p.next
                while(q!=None and q.val in G):
                    q=q.next
                p=q
            else:
                p=p.next

        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        curr_node = head
        no = 0
        while curr_node:
            if curr_node.val in G:
                curr_node = curr_node.__next__
                while curr_node and (curr_node.val in G):
                    curr_node = curr_node.__next__
                no = no + 1
            else:
                curr_node = curr_node.__next__
        return no


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        curr_node = head
        value_in = False
        no = 0
        while curr_node:
            if value_in and (not curr_node.val in G):
                no = no + 1
                value_in = False
            elif curr_node.val in G:
                value_in = True
            curr_node = curr_node.__next__
        if value_in:
            no = no + 1
        return no


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        while head:
            if head.val in G:
                count += 1
                while head and head.val in G:
                    head = head.next
            else:
                head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        count = 0
        while(head):
            if(head.val in G):
                while(head.next and head.next.val in G):
                    head = head.next
                count += 1
            head = head.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        temp = head
        count = 0
        while temp:
            if temp.val in G:
                while temp and temp.val in G:
                    temp = temp.next
                count += 1
                if not temp:
                    break
            temp = temp.next
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        Gset = set(G)
        cur = head
        noOfcomponents = 0
        while cur:
            if cur.val in Gset and (not cur.__next__ or cur.next.val not in Gset):
                noOfcomponents+=1
                cur = cur.__next__
            else:
                cur = cur.__next__
        return noOfcomponents


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        temp = head
        while(temp):
            if(temp.val in G):
                count = count + 1
                while(temp and temp.val in G):
                    temp = temp.__next__
            else:
                temp = temp.__next__
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        while(head and head.next):
            if head.val in G and head.next.val in G:
                G.remove(head.val)
            head = head.next
        return len(G)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        lst=[]
        curr=head
        while curr:
            lst.append(curr.val)
            curr=curr.next
        
        count=0
        i=0
        flag=0
        while i <len(lst):
            if lst[i] in G:
                i=i+1
                flag=1
                continue
            elif flag==1 and lst[i] not in G:
                count=count+1
                i=i+1
                flag=0
            else:
                i=i+1
                
        if lst[-1] in G:
            count=count+1
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        '''
        # approach 1
        # traverse ll, if node in G, put in components as another list or extending the list
        
        num_components=0
        components=[]
        
        cur=head
        dummy=ListNode(-1)
        dummy.next=cur
        
        while cur:
            if cur.val in G:
                if dummy.val in G:
                    component=components[-1]
                    components.pop()
                    component.append(cur.val)
                    components.append(component)
                else:
                    components.append([cur.val])
            dummy=cur
            cur=cur.next
        
        print(len(components))
        return len(components)
        '''
        # approach 2 : 
        # traverse ll, check if prev node in G. use a flag
        # if not prev_in : increment count, else continue traversal (going through the same component)
        
        cur=head
        prev_in=False
        count=0
        
        while cur:
            if cur.val in G:
                if not prev_in:
                    count+=1
                prev_in=True
            else:
                prev_in=False
            cur=cur.__next__
        return count
                    
                    
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        temp=head
        count=0
        c=0
        if len(G)==1:
            return 1
        while temp :
            if temp.val  in G :
                    print((temp.val))
                    count+=1
                    while temp and temp.val in G:
                        temp=temp.__next__ 
            else:
                temp=temp.__next__
                
            
        return count
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        if len(G)==1:
            return 1
        while head :
            if head.val  in G :
                    print((head.val))
                    count+=1
                    while head and head.val in G:
                        head=head.__next__ 
            else:
                head=head.__next__
                
            
        return count
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        
        while head:
            if head.val in G:
                ind = G.index(head.val)
                count+=1
                head=head.__next__
                ind+=1
                while head and head.val in G:
                    head=head.__next__
                
            else:
                head=head.__next__
        return(count)        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        cur = head
        connected = 0
        
        while cur != None:
            if cur.val in G:
                while cur.val in G:
                    cur = cur.next
                    
                    if cur == None:
                        break
                        
                connected += 1
            else:
                cur = cur.next
        
        return connected

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count = 0
        while head:
            if head.val in G and (head.__next__ == None or head.next.val not in G):
                count += 1
            head = head.__next__
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
    
        count=0
        i=head
        while i:
            if i.val in G:
                count+=1
                while i and i.val in G:
                    i=i.__next__
            else :i=i.__next__
        return count


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        temp=head
        new=[]
        
        while temp:
            new.append(temp.val)
            temp=temp.__next__
        
        dkg={}
        
        for i in G:
            dkg[i]=1
                
        for i in range(len(new)):
            if new[i] in dkg:
                new[i]=1
            else:
                new[i]=0
        
        count=new[0]
        for i in range(1,len(new)):
            if new[i]!=new[i-1] and new[i]==1:
                count+=1


        return count


            
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        count = 0
        p1, p2 = head, head
        
        while p2:
            if p1.val in G:
                p2 = p1.next
                p1 = p2
                if not p2 or p2.val not in G:
                    count+=1
            else:
                p1 = p2.next
                p2 = p1
        
        return count

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        counter = 0
        prev, current = None, head
        
        while current:
            if current.val in G:
                if not prev or prev.val not in G:
                    counter += 1
                    
            prev, current = current, current.__next__
            
        return counter


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        c=head
        a=0
        while c:
            if (c.val in G and getattr(c.next,'val',None) not in G):
                a=a+1
            c=c.next
        return a

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        cnt = 0
        while head:
            if head.val in G and (head.__next__ is None or head.next.val not in G):
                cnt+=1
            head = head.__next__
        return cnt


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        initial_c = len(G)
        
        runner = head
        # Approach 1
#         ans = []
#         conn_ll = []
#         while runner:
#             if runner.val in G:
#                 conn_ll.append(runner.val)
#             else:
#                 if conn_ll:
#                     ans.append(conn_ll[:])
#                     conn_ll = []
#             runner = runner.next
            
#         if conn_ll:
#             ans.append(conn_ll)

#         return len(ans)

        # Approach 2
        count = 0
        while runner:
            if runner.val in G and getattr(runner.next, 'val', None) not in G:
                count += 1
            runner = runner.next
        return count 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        cur = head
        N = len(G)
        while cur:
            if cur.__next__ and cur.val in G and cur.next.val in G:
                N-=1
            cur = cur.__next__
        return N
                
                


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        
        res =0
        curr = head
        found = False
        while curr is not None:
            if not found and curr.val in G:
                found = True
                res +=1
                
            if found and curr.val  not in G:
                found = False
            curr = curr.__next__
        return res


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        count=0
        s=set(G)
        ans=len(G)
        while head and head.__next__:
            if (head.val in G) and (head.next.val in G):
                ans-=1
            head=head.__next__
        return ans