Problem
题目大意:给你一个链表,再给你一些合法的节点,问你链表中有多少个连通分量(所有节点必须合法)。
https://leetcode.com/problems/linked-list-components/description/
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 byhead
,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.
Solution1: Graph Traversal using DFS
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 |
// Author: Huahua // Running time: 76 ms class Solution { public: int numComponents(ListNode* head, vector<int>& G) { unordered_set<int> f(G.begin(), G.end()); unordered_map<int, vector<int>> g; int u = head->val; while (head->next) { head = head->next; int v = head->val; if (f.count(v) && f.count(u)) { g[u].push_back(v); g[v].push_back(u); } u = v; } int ans = 0; unordered_set<int> visited; for (int u : G) { if (visited.count(u)) continue; ++ans; dfs(u, g, visited); } return ans; } private: void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) { if (visited.count(cur)) return; visited.insert(cur); for (const int next : g[cur]) dfs(next, g, visited); } }; |
Solution 2: Count tail node in sub graph
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua // Running time: 35 ms class Solution { public: int numComponents(ListNode* head, vector<int>& G) { unordered_set<int> g(G.begin(), G.end()); int ans = 0; while (head) { if (g.count(head->val) && (!head->next || !g.count(head->next->val))) ++ans; head = head->next; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment