Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #include <cstring>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#pragma GCC optimize("Ofast")
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define mp make_pair
- #define pb push_back
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 1e5 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"🚗", "🚕", "🚙"};
- struct dsu {
- int p[N], s[N], ans[N];
- set < pii > a[N];
- dsu() {
- iota(p, p + N, 0);
- memset(s, 1, sizeof s);
- }
- int find(int u) {
- return (p[u] == u ? u : p[u] = find(p[u]));
- }
- void add_friend(int u, int v) {
- if (find(u) == find(v)) {
- ans[u]++;
- ans[v]++;
- }
- else {
- int x = find(u);
- int y = find(v);
- a[x].insert({ u, v });
- a[y].insert({ v, u });
- }
- }
- void add_edge(int u, int v) {
- int x = find(u);
- int y = find(v);
- if (x != y) {
- if (s[x] < s[y]) {
- p[x] = y;
- s[y] += s[x];
- for (auto it = a[x].begin(); it != a[x].end(); ) {
- auto [n1, n2] = *it;
- if (find(n2) == y) {
- ans[n1]++;
- ans[n2]++;
- a[y].erase({ n2, n1 });
- auto ptr = ++it;
- a[x].erase(--it);
- it = ptr;
- }
- else {
- a[y].insert(*it);
- it++;
- }
- }
- }
- else {
- p[y] = x;
- s[x] += s[y];
- for (auto it = a[y].begin(); it != a[y].end(); ) {
- auto [n1, n2] = *it;
- if (find(n2) == x) {
- ans[n1]++;
- ans[n2]++;
- a[x].erase({ n2, n1 });
- auto ptr = ++it;
- a[y].erase(--it);
- it = ptr;
- }
- else {
- a[x].insert(*it);
- it++;
- }
- }
- }
- }
- }
- } a;
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(9);
- ios::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- int n, m, k;
- cin >> n >> m >> k;
- for (int i = 0; i < m; i++) {
- int u, v;
- cin >> u >> v;
- a.add_friend(u, v);
- }
- for (int i = 0; i < k; ++i) {
- int u, v;
- cin >> u >> v;
- a.add_edge(u, v);
- }
- int q;
- cin >> q;
- while (q--) {
- char c;
- cin >> c;
- if (c == '?') {
- int x;
- cin >> x;
- cout << a.ans[x] << "\n";
- }
- else {
- int u, v;
- cin >> u >> v;
- if (c == 'T') {
- a.add_edge(u, v);
- }
- else {
- a.add_friend(u, v);
- }
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment