bool_bool

247 - pending

Nov 30th, 2019
250
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(v) v.begin(), v.end()
  5. #define Chrono chrono::steady_clock::now().time_since_epoch().count()
  6. #define dist2D(x1, y1, x2, y2) ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
  7. #define dist3D(x1, y1, z1, x2, y2, z2) ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2))
  8. #define EPS 1e-15
  9. #define eb emplace_back
  10. #define endl "\n"
  11. #define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  12. #define FI freopen("in.txt", "r", stdin)
  13. #define FO freopen("out.txt", "w", stdout)
  14. #define ff first
  15. #define INF 1000000000000000000
  16. #define ld long double
  17. #define ll long long
  18. #define mem(x,y) memset(x, y, sizeof x)
  19. #define mp make_pair
  20. #define mt make_tuple
  21. #define msi map<string, int>
  22. #define mii map<int, int>
  23. #define mis map<int, string>
  24. #define MOD 1000000007
  25. #define PI acos(-1.0)
  26. #define PQ priority_queue
  27. #define pb push_back
  28. #define pib pair<int, bool>
  29. #define pii pair<int, int>
  30. #define pll pair<ll, ll>
  31. #define present(c, x) ((c).find(x) != (c).end())
  32. #define sfi(x) scanf("%d", &x)
  33. #define sfii(x,y) scanf("%d %d", &x, &y)
  34. #define sfiii(x,y,z) scanf("%d %d %d", &x, &y, &z)
  35. #define siz(x) (int)x.size()
  36. #define ss second
  37. #define timeTaken endd = clock(); cout << (double) (endd - beginn) / CLOCKS_PER_SEC * 1000 << endl
  38. #define timeInit clock_t beginn = clock(), endd
  39. #define ull unsigned long long
  40. #define umsi unordered_map<string, int>
  41. #define umii unordered_map<int, int>
  42. #define umis unordered_map<int, string>
  43. #define vb vector<bool>
  44. #define vi vector<int>
  45. #define vvi vector<vi>
  46. #define vii vector<pii>
  47. #define vvii vector<vii>
  48. #define vll vector<ll>
  49. #define vvll vector<vll>
  50. #define vpll vector<pll>
  51. #define bug(...) cerr << __LINE__ << " : (" << #__VA_ARGS__ << ") = ("; _Print(__VA_ARGS__);
  52. template<class T> void _Print(T &&x) { cerr << x << ")" << endl; }
  53. template<class T, class ...S> void _Print(T &&x, S &&...y) { cerr << x << ", "; _Print(y...); }
  54.  
  55.  
  56. #include <ext/pb_ds/assoc_container.hpp>
  57. #include <ext/pb_ds/tree_policy.hpp>
  58. #include <functional>
  59. using namespace __gnu_pbds;
  60. typedef tree<int,null_type, less<int>, rb_tree_tag,
  61. tree_order_statistics_node_update> ordered_set;
  62.  
  63. //os.order_of_key(v): returns how many elements strictly less than v
  64. //os.find_by_order(k - 1): returns kth smallest element's iterator
  65.  
  66.  
  67. template<class T> class compare {
  68. public:
  69. bool operator() (pair<T, T> &x, pair<T, T> &y) {
  70. if (x.first == y.first) {
  71. return x.ss > y.ss;
  72. }
  73. return x.ff > y.ff;
  74. }
  75. };
  76.  
  77. template<class T> ostream &operator<<(ostream &os, const pair<T, T> &a) { return os << a.ff << " " << a.ss; }
  78. ll power(ll a, int b) {
  79. ll po = 1;
  80. while (b) {
  81. if (b & 1)
  82. po *= a;
  83. a *= a;
  84. b >>= 1;
  85. }
  86. return po;
  87. }
  88.  
  89. template<class T> pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff + b.ff, a.ss + b.ss}; }
  90. template<class T> pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff - b.ff, a.ss - b.ss}; }
  91. template<class T> pair<T, T> operator*(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff * b.ff, a.ss * b.ss}; }
  92. template<class T> pair<T, T> operator%(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff % b.ff, a.ss % b.ss}; }
  93. template<class T, class U> pair<T, T> operator+(const pair<T, T> &a, const U &b) { return {a.ff + b, a.ss + b}; }
  94. template<class T, class U> pair<T, T> operator*(const pair<T, T> &a, const U &b) { return {a.ff * b, a.ss * b}; }
  95.  
  96. int Set(int N, int pos) { return N = N | (1 << pos); }
  97. int reset(int N, int pos){ return N = N & ~ (1 << pos); }
  98. bool check(int N, int pos){ return (bool) (N & (1 << pos)); }
  99.  
  100. ///=======================================template=======================================///
  101.  
  102. int n, m;
  103. vvi g, SCC;
  104. vi dfs_num, dfs_low, Stack, vis;
  105. int dtime, numofChildren;
  106.  
  107. void tarjan_SCC(int u) {
  108. vis[u] = 1;
  109. dfs_num[u] = dfs_low[u] = ++dtime;
  110. Stack.eb(u);
  111.  
  112. for (auto &v : g[u]) {
  113. if (dfs_num[v] == INT_MAX) {
  114. tarjan_SCC(v);
  115. }
  116. if(vis[u])
  117. dfs_low[u] = min(dfs_low[u], dfs_low[v]);
  118. }
  119.  
  120. if (dfs_low[u] >= dfs_num[u]) {
  121. vi temp;
  122. int v;
  123. do {
  124. v = Stack.back();
  125. Stack.pop_back();
  126. temp.pb(v);
  127. vis[v] = 0;
  128. } while (v != u);
  129. SCC.eb(temp);
  130. }
  131. }
  132.  
  133. int main() {
  134. //FI;FO;
  135. //FastIO; //timeInit;
  136.  
  137. int ds = 0;
  138. while (cin >> n >> m and (m | n)) {
  139. SCC.clear();
  140.  
  141. if (ds != 0)
  142. cout << endl;
  143. umis getst;
  144. umsi saves;
  145. g.assign(n, vi());
  146. dfs_num.assign(n, INT_MAX);
  147. dfs_low.assign(n, INT_MAX);
  148. vis.assign(n, 0);
  149. dtime = 0;
  150. int cnt = -1;
  151. while (m--) {
  152. string from, to;
  153. cin >> from >> to;
  154. if (!present(saves, from)) {
  155. saves[from] = ++cnt;
  156. getst[cnt] = from;
  157. }
  158. if (!present(saves, to)){
  159. saves[to] = ++cnt;
  160. getst[cnt] = to;
  161. }
  162. g[saves[from]].eb(saves[to]);
  163. }
  164.  
  165. for (int i = 0; i < n; i++) {
  166. if (dfs_num[i] == INT_MAX) {
  167. tarjan_SCC(i);
  168. }
  169. }
  170.  
  171. cout << "Calling circles for data set " << ++ds <<":" << endl;
  172. for (auto &x : SCC) {
  173. cout << getst[x[0]];
  174. for (int j = 1; j < siz(x); j++) {
  175. cout << ", " << getst[x[j]];
  176. }
  177. cout << endl;
  178. }
  179.  
  180. }
  181.  
  182.  
  183. //timeTaken;
  184. return 0;
  185. }
Advertisement
Add Comment
Please, Sign In to add comment