Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const int maxn = 100000;
- int dsu[maxn*2], rank[maxn*2];
- void dsu_init(int n)
- {
- for (int i = 0; i < 2*n; i++)
- {
- dsu[i] = i;
- rank[i] = 0;
- }
- }
- int dsu_find(int a)
- {
- if (dsu[a] == a) return a;
- return dsu[a] = dsu_find(dsu[a]);
- }
- bool _dsu_unite(int a, int b)
- {
- a = dsu_find(a);
- b = dsu_find(b);
- if (a == b) return 1;
- if ((a^1) == b) return 0;
- if (rank[a] < rank[b])
- {
- dsu[a] = b;
- }
- else if(rank[a] > rank[b])
- {
- dsu[b] = a;
- }
- else
- {
- dsu[a] = b;
- rank[b]++;
- }
- return 1;
- }
- bool dsu_unite_different(int a, int b)
- {
- a = dsu_find(2*a);
- b = dsu_find(2*b);
- return _dsu_unite(a, b^1) && _dsu_unite(a^1, b);
- }
- bool dsu_unite_same(int a, int b)
- {
- a = dsu_find(2*a);
- b = dsu_find(2*b);
- return _dsu_unite(a, b) && _dsu_unite(a^1, b^1);
- }
- void dsu_write_example(int n)
- {
- cout << "First: ";
- for (int i = 0; i < 2*n; i+=2)
- {
- if (dsu_find(i)&1)
- {
- cout << i/2+1 << " ";
- }
- }
- cout << endl << "Second: ";
- for (int i = 0; i < 2*n; i+=2)
- {
- if (!(dsu_find(i)&1))
- {
- cout << i/2+1 << " ";
- }
- }
- cout << endl;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- int n, m, a, b;
- char c;
- cin >> n >> m;
- dsu_init(n);
- for (int i = 0; i < m; i++)
- {
- cin >> c;
- if (c == 's')
- {
- cin >> a >> b;
- if (!dsu_unite_same(a-1, b-1))
- {
- cout << "ERROR";
- return 0;
- }
- }
- else if (c == 'd')
- {
- cin >> a >> b;
- if(!dsu_unite_different(a-1, b-1))
- {
- cout << "ERROR";
- return 0;
- }
- }
- else
- {
- dsu_write_example(n);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement