Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX = 1e5+5;
- map<string, int> to;
- string a, b;
- vector<int> order, gr[MAX];
- int n, used[MAX], comp[MAX];
- int cnt_comp[MAX], cmp, ans;
- void dfs(int u) {
- used[u] = true;
- for (int to : gr[u]) {
- if (!used[to]) {
- dfs(to);
- }
- }
- order.push_back(u);
- }
- void dfs2(int u, int cmp) {
- used[u] = 2;
- comp[u] = cmp;
- ++cnt_comp[comp[u]];
- if (cnt_comp[comp[u]] == 2) ++ans;
- for (int to : gr[u]) if (used[to] != 2) {
- dfs2(to, cmp);
- }
- }
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- while (cin >> a >> b) {
- if (!to.count(a)) {
- to[a] = n++;
- }
- if (!to.count(b)) {
- to[b] = n++;
- }
- int s = to[a], t = to[b];
- gr[s].push_back(t);
- }
- for (int i = 0; i < n; ++i) {
- if (!used[i]) dfs(i);
- }
- for (int i = 0; i < n; ++i) {
- int u = order[i];
- if (used[u] != 2) {
- dfs2(u, cmp);
- ++cmp;
- }
- }
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement