Advertisement
danielvitor23

Untitled

Apr 16th, 2021
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1e5+5;
  4.  
  5. map<string, int> to;
  6. string a, b;
  7.  
  8. vector<int> order, gr[MAX];
  9. int n, used[MAX], comp[MAX];
  10. int cnt_comp[MAX], cmp, ans;
  11.  
  12. void dfs(int u) {
  13. used[u] = true;
  14. for (int to : gr[u]) {
  15. if (!used[to]) {
  16. dfs(to);
  17. }
  18. }
  19. order.push_back(u);
  20. }
  21.  
  22. void dfs2(int u, int cmp) {
  23. used[u] = 2;
  24. comp[u] = cmp;
  25. ++cnt_comp[comp[u]];
  26. if (cnt_comp[comp[u]] == 2) ++ans;
  27. for (int to : gr[u]) if (used[to] != 2) {
  28. dfs2(to, cmp);
  29. }
  30. }
  31.  
  32. int main() {
  33. ios_base::sync_with_stdio(0), cin.tie(0);
  34. while (cin >> a >> b) {
  35. if (!to.count(a)) {
  36. to[a] = n++;
  37. }
  38. if (!to.count(b)) {
  39. to[b] = n++;
  40. }
  41. int s = to[a], t = to[b];
  42. gr[s].push_back(t);
  43. }
  44. for (int i = 0; i < n; ++i) {
  45. if (!used[i]) dfs(i);
  46. }
  47. for (int i = 0; i < n; ++i) {
  48. int u = order[i];
  49. if (used[u] != 2) {
  50. dfs2(u, cmp);
  51. ++cmp;
  52. }
  53. }
  54. cout << ans << '\n';
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement