fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class DSU
  6. {
  7. 	public :
  8. 	unordered_map<string,int> size;
  9. 	unordered_map<string,string> parent;
  10. 	DSU(unordered_set<string> ele)
  11. 	{
  12. 		for(auto it : ele)
  13. 		{
  14. 			parent[it]=it;
  15. 			size[it] =1;
  16. 		}
  17. 	}
  18.  
  19. 	string findParent(string curr)
  20. 	{
  21. 		if(curr==parent[curr])
  22. 		return curr;
  23. 		else
  24. 		{
  25. 			return parent[curr]=findParent(parent[curr]);
  26. 		}
  27. 	}
  28.  
  29. 	void doUnion (string firstPerson,string secondPerson)
  30. 	{
  31. 		string firstPersonParent = findParent(firstPerson);
  32. 		string secondPersonParent = findParent(secondPerson);
  33.  
  34. 		if(firstPersonParent==secondPersonParent)
  35. 		return;
  36. 		if(size[firstPersonParent] > size[secondPersonParent])
  37. 		{
  38. 			size[firstPersonParent] += size[secondPersonParent];
  39. 			parent[secondPersonParent] = firstPersonParent;
  40. 		}
  41. 		else
  42. 		{
  43. 			size[secondPersonParent] += size[firstPersonParent];
  44. 			parent[firstPersonParent] = secondPersonParent;
  45. 		}
  46. 	}
  47. };
  48.  
  49. string findMinTime(vector<string> logs)
  50. {
  51. 	vector<vector<string>> adj;
  52. 	unordered_set<string> friends;
  53. for(auto it : logs)
  54.     {
  55.     	stringstream ss(it);
  56.     	string firstPerson;
  57.     	string secondPerson;
  58.     	string relation;
  59.     	string time;
  60.     	ss>>time>>firstPerson>>relation>>secondPerson;
  61.     	vector<string> temp;
  62.     	temp.push_back(time);
  63.     	temp.push_back(firstPerson);
  64.     	temp.push_back(secondPerson);
  65.     	friends.insert(secondPerson);
  66.     	friends.insert(firstPerson);
  67.     	adj.push_back(temp);
  68.     }
  69.     DSU dsu(friends);
  70.     int total = friends.size();
  71.  
  72.     for(auto it : adj )
  73.     {
  74.     	string time = it[0];
  75.     	string firstPerson = it[1];
  76.     	string secondPerson = it[2];
  77.     	if(dsu.findParent(firstPerson)!= dsu.findParent(secondPerson))
  78.     	{
  79.     		dsu.doUnion(firstPerson,secondPerson);
  80.     		total--;
  81.     		if(total==1)
  82.     		return time;
  83.     	}
  84.     }
  85.     return "No connected";
  86.  
  87. }
  88.  
  89. int main() {
  90. 	// your code goes here
  91. 	 vector<string> logs = {
  92.         "167001 Alice shared-ride-with Bob",
  93.         "167003 Charlie shared-ride-with Dan",
  94.         "167008 Bob shared-ride-with Charlie",
  95.         "167010 Alice shared-ride-with Eve",
  96.         "167020 Bob shared-ride-with Dan"
  97.     };
  98.     cout<<findMinTime (logs);
  99. 	return 0;
  100. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
167010
https://ideone.com/PJTxOS
language:
C++ (gcc 8.3)
created:
3 days 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!