Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.58 KB | None | 0 0
  1. /***"In the name of Allah(swt), the most gracious, most merciful. Allah(swt) blesses with knowledge whom he wants."***/
  2. /*Header file starts here*/
  3. //#include<bits/stdc++.h>
  4. #include<vector>
  5. #include<list>
  6. #include<map>
  7. #include<set>
  8. #include<queue>
  9. #include<stack>
  10. #include<bitset>
  11. #include<algorithm>
  12. #include<iostream>
  13. #include<iomanip>
  14. #include<cstdio>
  15. #include<cmath>
  16. #include<cstdlib>
  17. #include<iterator>
  18. #include<cctype>
  19. #include<climits>
  20. #include<string>
  21. #include<sstream>
  22. #include<cstring>
  23. #include<ctime>
  24. /*Header file ends here*/
  25.  
  26. /*Macro starts here*/
  27. #define fasterInOut ios::sync_with_stdio(false); cin.tie(0);
  28. #define fin(in) freopen("in.txt", "r", stdin)
  29. #define fout(out) freopen("out.txt", "w", stdout)
  30. #define pb push_back
  31. #define ll long long
  32. #define lld I64d//for CF submissions
  33. #define rh cout<<"Reached Here\n"
  34. #define inf LLONG_MAX
  35. #define neginf LLONG_MIN
  36. #define forit(it,s) for(__typeof((s).end()) it=(s).begin(); it!= (s).end(); it++)
  37. #define string_reverse(s) reverse(s.begin(), s.end())//Vector also can be reversed with this function
  38. #define memz(x) memset(x, 0, sizeof(x));
  39. #define memneg(x) memset(x, -1, sizeof(x));
  40.  
  41. //Geometry & Maths
  42. #define gcd(a,b) __gcd(a,b)
  43. #define lcm(a, b) (a*b)/gcd(a, b)
  44. #define pi acos(-1.0)
  45. #define negmod(ans, x, m) ll y= (-1*x)%m; if(y== 0) ans= 0; else ans= m-y;//for negative mod only i.e. when x<0. Undefined when m<0
  46. #define dis(x1, y1, x2, y2) sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
  47. #define t_area(a, b, c, s) sqrt(s*(s-a)*(s-b)*(s-c))//  s= (a+b+c)/2.0
  48. #define t_angle(a, b, c) acos((a*a+b*b-c*c)/(2*a*b))// returns angle C in radian. a, b, c are anti-clockwise formatted and side a and b form angle C
  49. #define pointPos(x1, y1, x2, y2, x3, y3) ((x2-x1)*(y3-y1))-((x3-x1)*(y2-y1));/*returns NEGATIVE if the Point P3 is on the RIGHT side of the line P1P2,
  50. otherwise returns POSITIVE in case of LEFT and ZERO when the point is on the line*/
  51. #define t_areaWithPoints(x1, y1, x2, y2, x3, y3) abs(0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)));//returns the area of a triangle formed by P1, p2, p3
  52.  
  53. //Base Conversions
  54. #define toBin(bin, n) bin= bitset<8>(n).to_string()//returns a corresponding 8 bit Binary string 'bin' of integer 'n'
  55. #define toOct(oct, n, ch) /*char ch[100]*/sprintf(ch, "%o", n); oct= ch;//returns a string 'oct'(maximum 100 length): Octal represent of number 'n'
  56. #define toHex(hex, n, ch) /*char ch[100]*/sprintf(ch, "%x", n); hex= ch;//returns a string 'hex'(maximum 100 length): Hexadecimal represent of number 'n'
  57. #define intToString(s, n, itos) /*stringstream itos;*/ itos<<n; s= itos.str();//converts a number 'n' to a string 's'
  58. #define stringToint(n, s) stringstream stoi(s); stoi>>n;//converts a string 's' to a number 'n'---ONLY ONCE USABLE---
  59.  
  60. //Others
  61. #define substring(s1, s2) strstr(s1.c_str(), s2.c_str())//returns true if s1 contains s2 in O(n^2) complexity
  62. #define strCharRemove(s, c) s.erase(remove(s.begin(), s.end(), c), s.end());//Removes all character 'c' from the string 's'
  63. #define strLastCharRemove(s) s.erase(s.end()-1)//Removes last(position is given by s.end()-1) character form string 's'
  64. #define vectorEraseSingle(v, pos) v.erase(v.begin()+pos)//Erases an element from "pos' position in zero based index from the vector 'v'
  65. #define vectorEraseRange(v, spos, fpos) v.erase(v.begin()+spos, v.begin()+fpos)//Erases range inclusive spos' to EXCLUSIVE(without) 'fpos' from vector 'v'
  66. #define lowerBound(v, elem) (lower_bound(v.begin(), v.end(), elem))-v.begin();/*returns the lower bound of 'elem' in integer(ZERO BASED INDEX), where lower bound means
  67. the LEFTMOST index where there is any integer which is GREATER OR EQUAL to 'elem'.*/
  68. #define upperBound(v, elem) (upper_bound(v.begin(), v.end(), elem))-v.begin();/*returns the upper bound of 'elem' in integer(ZERO BASED INDEX), where upper bound means
  69. the LEFTMOST index where there is any integer which is GREATER than 'elem'.*/
  70. #define setLowerBound(st, elem) st.lower_bound(elem);/*returns the lower bound ITERATOR of 'elem' in the stl set 'st', where lower bound means
  71. the LEFTMOST index where there is any integer which is GREATER OR EQUAL to 'elem'.*/
  72. #define setUpperBound(st, elem) st.upper_bound(elem);/*returns the upper bound ITERATOR of 'elem' in the stl set 'st', where upper bound means
  73. the LEFTMOST index where there is any integer which is GREATER than 'elem'.*/
  74. #define clearPQ(pq, type) pq= priority_queue<type>()/*It clears a priority queue by redeclaration*/
  75. #define minPQ(PQ_name, type) priority_queue<type, vector<type>, greater<type> > PQ_name;/*min priority queue with built in type i.e int or long long etc. */
  76. #define sortArr(arr, sz) sort(arr+1, arr+(sz+1));/*Sorts an array from index 1 to index 'sz'*/
  77. /*Macro ends here*/
  78.  
  79. /*Frequently used Function starts here*/
  80. //Bit set
  81. /*ll Set(ll mask, ll pos){return mask = (mask OR ((ll)1<<pos));}*//*Sets pos'th bit HIGH of the mask and returns*//**Replace OR by Bitwise OR sign when using**/
  82. bool check(ll mask, ll pos){ return (bool)(mask & ((ll)1 << pos)); }/*Checks if the pos'th bit is HIGH or not of the mask*/
  83. /*Frequently used Function ends here*/
  84.  
  85. using namespace std;
  86.  
  87.  
  88. struct data
  89. {
  90.     ll a, b, c;
  91.     data(ll x, ll y, ll z)
  92.     {
  93.         a = x, b = y, c = z;
  94.     }
  95.  
  96.     bool operator <(const data &dt) const
  97.     {
  98.         if (dt.a == a)
  99.         {
  100.             if (dt.b == b)
  101.             {
  102.                 return dt.c < c;
  103.             }
  104.             else
  105.             {
  106.                 return dt.b < b;
  107.             }
  108.         }
  109.         else
  110.         {
  111.             return dt.a < a;
  112.         }
  113.     }
  114. };
  115.  
  116. struct node
  117. {
  118.     ll a, b;
  119.     node(ll x, ll y)
  120.     {
  121.         a = x, b = y;
  122.     }
  123.  
  124.     bool operator < (const node& nd) const
  125.     {
  126.         if (nd.a == a) return nd.b < b;
  127.         return nd.a < a;
  128.     }
  129. };
  130.  
  131. vector<vector<ll> > g;
  132. vector<ll> vis;
  133. ll src;
  134. void dfs(ll u)
  135. {
  136.     vis[u] = 1;
  137.     ll i;
  138.     if (g[u].size() == 1)
  139.     {
  140.         src = u;
  141.     }
  142.     for (i = 0; i < g[u].size(); i++)
  143.     {
  144.         ll v = g[u][i];
  145.         if (!vis[v])
  146.         {
  147.             dfs(v);
  148.         }
  149.     }
  150.     return;
  151. }
  152. int main()
  153. {
  154.     //fasterInOut;
  155.     ll n;
  156.     cin >> n;
  157.     ll i;
  158.     vector<data> v;
  159.     for (i = 1; i <= (n - 2); i++)
  160.     {
  161.         ll a, b, c;
  162.         cin >> a >> b >> c;
  163.         v.push_back(data(a, b, c));
  164.     }
  165.  
  166.     map<node, vector<ll> > mp;
  167.  
  168.     for (i = 0; i < v.size(); i++)
  169.     {
  170.         ll a = v[i].a;
  171.         ll b = v[i].b;
  172.         ll c = v[i].c;
  173.         mp[node(a, b)].pb(i);
  174.         mp[node(b, c)].pb(i);
  175.         mp[node(c, a)].pb(i);
  176.     }
  177.     g = vector<vector<ll> >(n + 5);
  178.     vis = vector<ll>(n + 5, 0);
  179.     ll p;
  180.     for (auto it = mp.begin(); it != mp.end(); it++)
  181.     {
  182.         vector<ll> tmp = it->second;
  183.         if (tmp.size() == 2)
  184.         {
  185.            
  186.             ll u = tmp[0];
  187.             ll v = tmp[1];
  188.             p = u;
  189.             g[u].push_back(v);
  190.             g[v].push_back(u);
  191.         }
  192.     }
  193.     src = -1;
  194.     dfs(p);
  195.     cout << "Source: " << src << endl;
  196.  
  197.  
  198.     char character;
  199.     cin >> character;
  200.     return 0;
  201. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement