fork download 
  1. #include <iostream>
  2. # include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class DSU
  6.  
  7. {
  8. 	public :
  9. 	vector<int> parent;
  10. 	vector<int> size;
  11.  
  12. 	DSU (int n)
  13. 	{
  14. 		parent.resize(n);
  15. 		size.resize(n,1);
  16. 		for(int i=0;i<n;i++)
  17. 		{
  18. 			parent[i] = i;
  19. 		}
  20. 	}
  21.  
  22. 	int findParent(int x)
  23. 	{
  24. 		if(parent[x]==x)
  25. 		return x;
  26. 		else
  27. 		{
  28. 			parent[x] = findParent(parent[x]);
  29. 			return parent[x];
  30. 		}
  31. 	}
  32.  
  33. 	void unionBySize(int x,int y)
  34. 	{
  35. 		int parentX = findParent(x);
  36. 		int parentY = findParent(y);
  37. 		if(parentX == parentY)
  38. 		return;
  39. 		if(size[parentX] > size[parentY])
  40. 		{
  41. 			parent[parentY] = parentX;
  42. 			size[parentX] += size[parentY];
  43. 		}
  44. 		else
  45. 		{
  46. 			parent[parentX] = parentY;
  47. 			size[parentY] += size[parentX];	
  48. 		}
  49. 	}
  50.  
  51. };
  52.  
  53. int minTime (vector<vector<int>> logs,int distinctN)
  54. {
  55. 	int n = logs.size();
  56. 	int minTime = -1;
  57. 	DSU dsu(distinctN);
  58.  
  59. 	for(int i=0;i<n;i++)
  60. 	{
  61. 		int time = logs[i][0];
  62. 		int x= logs[i][1];
  63. 		int y= logs[i][2];
  64. 		dsu.unionBySize(x,y);
  65.  
  66. 		if(dsu.size[dsu.findParent(x)]==distinctN)
  67. 		return time;
  68.  
  69.  
  70. 	}
  71. 	return minTime;
  72. }
  73.  
  74. int main() {
  75. 	 // Test 1: Example case
  76.     vector<vector<int>> logs1 = {
  77.         {2, 0, 1},
  78.         {3, 1, 2},
  79.         {4, 2, 3}
  80.     };
  81.     unordered_set<int> set;
  82.     for(auto it : logs1)
  83.     {
  84.     	set.insert(it[1]);
  85.     	set.insert(it[2]);
  86.     }
  87.     cout << "Test 1: " << minTime(logs1, set.size()) << " (Expected: 4)\n";
  88.  
  89.     // Test 2: Already connected late
  90.     vector<vector<int>> logs2 = {
  91.         {5, 0, 1},
  92.         {6, 1, 2},
  93.         {7, 2, 3}
  94.     };
  95.     cout << "Test 2: " << minTime(logs2, 4) << " (Expected: 7)\n";
  96.  
  97.     // Test 3: Never fully connected
  98.     vector<vector<int>> logs3 = {
  99.         {1, 0, 1},
  100.         {2, 2, 3}
  101.     };
  102.     cout << "Test 3: " << minTime(logs3, 4) << " (Expected: -1)\n";
  103. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Test 1: 4 (Expected: 4)
Test 2: 7 (Expected: 7)
Test 3: -1 (Expected: -1)
https://ideone.com/Hm5MC1
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!