One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a…
- User
One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist.
To play the game, Alice draws a straight line and marks n points on it, indexed from 1 to n . Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs m operations of the following type:
She picks three integers ai , di (1≤di≤10 ), and ki . She selects points ai,ai+di,ai+2di,ai+3di,…,ai+ki⋅di and connects each pair of these points with arcs. After performing all m operations, she wants to know the number of connected components† these points form. Please help her find this number.
† Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105 ). The description of the test cases follows.
The first line of each test case contains two integers n and m (1≤n≤2⋅105 , 1≤m≤2⋅105 ).
The i -th of the following m lines contains three integers ai , di , and ki (1≤ai≤ai+ki⋅di≤n , 1≤di≤10 , 0≤ki≤n ).
It is guaranteed that both the sum of n and the sum of m over all test cases do not exceed 2⋅105 .
Output For each test case, output the number of connected components.
Example InputCopy 3 10 2 1 2 4 2 2 4 100 1 19 2 4 100 3 1 2 5 7 2 6 17 2 31 OutputCopy 2 96 61 Note In the first test case, there are n=10 points. The first operation joins the points 1 , 3 , 5 , 7 , and 9 . The second operation joins the points 2 , 4 , 6 , 8 , and 10 . There are thus two connected components: {1,3,5,7,9} and {2,4,6,8,10} .
In the second test case, there are n=100 points. The only operation joins the points 19 , 21 , 23 , 25 , and 27 . Now all of them form a single connected component of size 5 . The other 95 points form single-point connected components. Thus, the answer is 1+95=96 .
In the third test case, there are n=100 points. After the operations, all odd points from 1 to 79 will be in one connected component of size 40 . The other 60 points form single-point connected components. Thus, the answer is 1+60=61 . type in c++
- Assistant
To solve the problem of determining the number of connected components after performing a series of operations on points in a "Connect the Dots" game, we can employ the Union-Find (Disjoint Set Union) data structure. Here's a step-by-step breakdown of how to approach this problem:
Step-by-Step Reasoning:
-
Initialization:
- Connected Components: Initially, each of the
npoints is its own connected component. Therefore, we start withnconnected components. - Union-Find Setup: We'll use Union-Find to efficiently manage and merge these components as operations are performed.
- Connected Components: Initially, each of the
-
Processing Each Operation:
- For each operation defined by
ai,di, andki, we identify the points that need to be connected. - The points selected in this operation are:
ai, ai + di, ai + 2di, ..., ai + ki * di. - To combine these points into a single connected component:
- Choose the first point
aias a base. - Iterate through the remaining points in the sequence.
- Use the Union-Find
unionoperation to merge each subsequent point with the base. - Each successful merge (where two points were previously in different components) reduces the total number of connected components by 1.
- Choose the first point
- For each operation defined by
-
Final Count:
- After all operations are processed, the resulting number of connected components gives the desired output.
Implementation Considerations:
-
Efficiency: Given the constraints (with up to
2*10^5points and operations), it's essential to use an efficient Union-Find implementation with path compression and union by rank to ensure that operations are handled in near-constant time. -
Edge Cases: Ensure that all inputs are within the specified bounds and handle cases where
kiis zero (i.e., no additional points to connect).
Example Walkthrough:
Consider the first example:
- Test Case 1:
- Points: 1 through 10
- Operations:
- Connect points
1, 3, 5, 7, 9(di=2, ki=4) - Connect points
2, 4, 6, 8, 10(di=2, ki=4)
- Connect points
- After the first operation, points
1, 3, 5, 7, 9are connected. - After the second operation, points
2, 4, 6, 8, 10are connected. - Hence, there are 2 connected components.
Final Answer (C++ Implementation):
#include <bits/stdc++.h> using namespace std; // Fast IO struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); } }; struct UnionFind { vector<int> parent; vector<int> rank; UnionFind(int n){ parent.resize(n+1); rank.resize(n+1, 1); for(int i=0;i<=n;i++) parent[i]=i; } int find_set(int x){ if(parent[x] != x){ parent[x] = find_set(parent[x]); } return parent[x]; } bool union_set(int x, int y){ int fx = find_set(x); int fy = find_set(y); if(fx == fy) return false; if(rank[fx] < rank[fy]){ parent[fx] = fy; } else{ parent[fy] = fx; if(rank[fx] == rank[fy]){ rank[fx]++; } } return true; } }; int main(){ FastIO fio; int t; cin >> t; while(t--){ int n, m; cin >> n >> m; UnionFind uf(n); int count = n; for(int i=0;i<m;i++){ long long a, d, k; cin >> a >> d >> k; if(k ==0) continue; long long last = a + k*d; // Ensure last <=n // But problem statement guarantees 1<=a +k*d <=n // So proceed // Union a with a + d, a + 2d, ..., a + k*d // To optimize, iterate and union a with p_j // Each successful union reduces count by1 for(long long t_j=1; t_j <=k; t_j++){ long long p = a + t_j*d; if(p > n) break; // safety, though not needed if(uf.union_set(a, p)){ count--; } } } cout << count << "\n"; } }Explanation of the Code:
-
Fast I/O: To handle large input sizes efficiently, we disable synchronization with
stdioand untiecinfromcout. -
Union-Find Structure:
- Initialization: Each point starts as its own parent. The
rankarray helps optimize the union operations. - Find Operation: Implements path compression to flatten the structure for faster future queries.
- Union Operation: Merges two sets and returns
trueif a merge was successful (i.e., the sets were previously separate).
- Initialization: Each point starts as its own parent. The
-
Processing Test Cases:
- For each test case, we initialize the Union-Find structure with
npoints. - We iterate through each operation, connecting the necessary points and updating the count of connected components.
- Finally, we output the number of connected components after all operations are applied.
- For each test case, we initialize the Union-Find structure with
Conclusion:
This approach efficiently handles the problem constraints by leveraging the Union-Find data structure, ensuring that all operations are processed in near-constant time per operation, which is crucial given the large possible input sizes.
-