leetcode 817. Linked List Components

Posted on | In |

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 bool vis[10000];
class Solution {
public:
    map<int,vector<int> >g;
    int numComponents(ListNode* head, vector<int>& G) {
        unordered_set<int> s(G.begin(),G.end());
        
        while(head->next){
            int u=head->val;
            int v=head->next->val;
            if(s.count(u)&&s.count(v)) {
                g[u].push_back(v);
                g[v].push_back(u);//!!  0->1->2 [1,0] G集合不一定有序 所以是无向图
                cout<<u<<" "<<v<<endl;
            
            }
            head=head->next;            
            
        }
        int ans=0;
           memset(vis,0,sizeof(vis));
        for(auto g:G){
        if(vis[g]) continue;
          else{
               dfs(g,vis);
                ans++;
          } 
        }
       return ans;
        
        
        
    }
    void dfs(int cur,bool vis[]){
        if(vis[cur]) return;
       vis[cur]=true;
        for(int i=0;i<g[cur].size();i++){
            if(!vis[g[cur][i]]) dfs(g[cur][i],vis);
        }
        
    }
};