fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. class DSU
  5. {
  6. public :
  7. 	int n;
  8. 	vector<int> sz;
  9. 	vector<int> parent;
  10. 	DSU (int num)
  11. 	{
  12. 		n= num;
  13. 		sz.resize(num+1,1);
  14. 		parent.resize(num+1,1);
  15. 		for(int i=0;i<=num;i++)
  16. 		{
  17. 			parent[i]=i;
  18. 		}
  19. 	}
  20.  
  21. 	int findParent (int x)
  22. 	{
  23. 		if(x==parent[x])
  24. 		return x;
  25. 		else
  26. 		{
  27. 			return parent[x]= findParent(parent[x]);
  28. 		}
  29. 	}
  30. 	void unite(int x,int y)
  31. 	{
  32. 		int parentX = findParent(x);
  33. 		int parentY = findParent(y);
  34. 		if(sz[parentX] > sz [parentY])
  35. 		{
  36. 			parent[parentY]= parentX;
  37. 			sz[parentX] = sz[parentX] + sz[parentY];
  38. 		}
  39. 		else
  40. 		{
  41. 			parent[parentX]= parentY;
  42. 			sz[parentY] = sz[parentY] + sz[parentX];
  43. 		}
  44. 	}
  45. };
  46.  
  47. int earliestConnectedTimestamp(vector<string> riders,  vector<string> logs)
  48.  
  49. {
  50. 	int components = riders.size();
  51. 	long long int timestamp;
  52. 	string person1,person2,relation;
  53. 	DSU dsu(components);
  54. 	unordered_map <string,int> usertoID;
  55. 	int id=0;
  56. 	for(int i=0;i<riders.size();i++)
  57. 	{
  58. 		usertoID.insert({riders[i],++id});
  59. 	}
  60. 	for(auto it : logs)
  61. 	{
  62. 		stringstream ss(it);
  63. 		ss>>timestamp>>person1>>relation>>person2;
  64. 		if(dsu.findParent(usertoID[person1])!=dsu.findParent(usertoID[person2]))
  65. 		{
  66. 			dsu.unite(usertoID[person1],usertoID[person2]);
  67. 			components--;
  68. 		}
  69. 		if(components==1)
  70. 		{
  71. 			return timestamp;
  72. 		}
  73. 	}
  74. 	return 0;
  75. }
  76.  
  77. int main() {
  78. 	// your code goes here
  79. 	vector<string> riders = {
  80.         "Alice",
  81.         "Bob",
  82.         "Charlie",
  83.         "Dan",
  84.         "Eve"
  85.     };
  86.  
  87.     vector<string> logs = {
  88.         "1670000001 Alice shared-ride-with Bob",
  89.         "1670000042 Charlie shared-ride-with Dan",
  90.         "1670000450 Bob shared-ride-with Charlie",
  91.         "1670000501 Alice shared-ride-with Eve",
  92.         "1670000621 Bob shared-ride-with Dan"
  93.     };
  94.  
  95.     cout << earliestConnectedTimestamp(riders, logs) << endl;
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1670000501
https://ideone.com/ZaNpM8
language:
C++ (gcc 8.3)
created:
18 hours 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!