#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define _new malloc
#define _realloc realloc
#define _delete free
///HASH SET
int _linear_hash_correctCap(int cap){
if (cap <= 0)
return 1;
int x = cap;
while (x & (x - 1))
x &= x - 1;
if (x != cap)
x <<= 1;
return x;
}
unsigned int _inplace_linear_hash_function(void* key, int size){
unsigned int ans = 0;
char* poz = key;
while (size--){
ans = (ans * 257) + (*poz);
poz++;
}
return ans;
}
int _inplace_linear_hash_compare(void* A, void* B, int size){
char* a = A;
char* b = B;
while (size--){
if (*a != *b)
return 1;
a++;
b++;
}
return 0;
}
typedef struct{
void* table;
unsigned int size, cap;
int keySize, valSize, totSize;
} inplace_linear_hash_map_t;
void* _inplace_linear_hash_map_get_key_at(inplace_linear_hash_map_t* map, int poz);
void* _inplace_linear_hash_map_get_value_at(inplace_linear_hash_map_t* map, int poz);
char* _inplace_linear_hash_map_get_label_at(inplace_linear_hash_map_t* map, int poz);
void _inplace_linear_hash_map_set_key_at(inplace_linear_hash_map_t* map, int poz, void* key);
void _inplace_linear_hash_map_set_value_at(inplace_linear_hash_map_t* map, int poz, void* val);
void _inplace_linear_hash_map_set_label_at(inplace_linear_hash_map_t* map, int poz, char label);
void _inplace_linear_hash_map_inserter(void* key, void* val, void* context);
int _inplace_linear_hash_map_keep_going(inplace_linear_hash_map_t* map, int poz, void* key, int goIfIsNil);
int _inplace_linear_hash_map_search_for(inplace_linear_hash_map_t* map, void* key, int goIfIsNil);
void _inplace_linear_hash_map_calibrate(inplace_linear_hash_map_t* map);
void* inplace_linear_hash_map_new(int startCap, int keySize, int valSize);
void inplace_linear_hash_map_clear(inplace_linear_hash_map_t* map);
void inplace_linear_hash_map_delete(inplace_linear_hash_map_t* map);
void inplace_linear_hash_map_swap(inplace_linear_hash_map_t* A, inplace_linear_hash_map_t* B);
int inplace_linear_hash_map_contains(inplace_linear_hash_map_t* map, void* key);
int inplace_linear_hash_map_is_empty(inplace_linear_hash_map_t* map);
int inplace_linear_hash_map_get_size(inplace_linear_hash_map_t* map);
int inplace_linear_hash_map_get_capacity(inplace_linear_hash_map_t* map);
void* inplace_linear_hash_map_get_value_at(inplace_linear_hash_map_t* map, void* key);
void inplace_linear_hash_map_set_value_at(inplace_linear_hash_map_t* map, void* key, void* val);
void inplace_linear_hash_map_insert(inplace_linear_hash_map_t* map, void* key, void* val);
void inplace_linear_hash_map_erase(inplace_linear_hash_map_t* map, void* key);
void inplace_linear_hash_map_iterate(inplace_linear_hash_map_t* map, void (*iterate)(void*, void*, void*), void* context);
void* _linear_hash_map_nil = NULL;
///PRIVATE
void* _inplace_linear_hash_map_get_key_at(inplace_linear_hash_map_t* map, int poz){
return map -> table + poz * (map -> totSize);
}
void* _inplace_linear_hash_map_get_value_at(inplace_linear_hash_map_t* map, int poz){
return map -> table + poz * map -> totSize + map -> keySize;
}
char* _inplace_linear_hash_map_get_label_at(inplace_linear_hash_map_t* map, int poz){
return map -> table + poz * map -> totSize + map -> keySize + map -> valSize;
}
void _inplace_linear_hash_map_set_key_at(inplace_linear_hash_map_t* map, int poz, void* key){
memcpy(_inplace_linear_hash_map_get_key_at(map, poz), key, map -> keySize);
}
void _inplace_linear_hash_map_set_value_at(inplace_linear_hash_map_t* map, int poz, void* val){
memcpy(_inplace_linear_hash_map_get_value_at(map, poz), val, map -> valSize);
}
void _inplace_linear_hash_map_set_label_at(inplace_linear_hash_map_t* map, int poz, char label){
*_inplace_linear_hash_map_get_label_at(map, poz) = label;
}
void _inplace_linear_hash_map_inserter(void* key, void* val, void* context){
inplace_linear_hash_map_insert(context, key, val);
}
int _inplace_linear_hash_map_keep_going(inplace_linear_hash_map_t* map, int poz, void* key, int goIfIsNil){
char label = *_inplace_linear_hash_map_get_label_at(map, poz);
if (label == 0)
return 0;
if (label == 1)
return goIfIsNil;
return _inplace_linear_hash_compare(_inplace_linear_hash_map_get_key_at(map, poz), key, map -> keySize);
}
int _inplace_linear_hash_map_search_for(inplace_linear_hash_map_t* map, void* key, int goIfIsNil){
_inplace_linear_hash_map_calibrate(map);
int poz = _inplace_linear_hash_function(key, map -> keySize) & (map -> cap - 1), i = 0;
while (_inplace_linear_hash_map_keep_going(map, poz, key, goIfIsNil))
poz = (poz + ((i++) << 1) + 1) & (map -> cap - 1);
return poz;
}
void _inplace_linear_hash_map_calibrate(inplace_linear_hash_map_t* map){
if ( (map -> size << 1) < map -> cap )
return;
inplace_linear_hash_map_t* H = inplace_linear_hash_map_new(map -> cap << 1, map -> keySize, map -> valSize);
inplace_linear_hash_map_iterate(map, _inplace_linear_hash_map_inserter, H);
inplace_linear_hash_map_swap(H, map);
inplace_linear_hash_map_delete(H);
}
void* inplace_linear_hash_map_new(int startCap, int keySize, int valSize){
inplace_linear_hash_map_t* map = _new(sizeof(inplace_linear_hash_map_t));
startCap = _linear_hash_correctCap(startCap);
map -> size = 0;
map -> cap = startCap;
map -> keySize = keySize;
map -> valSize = valSize;
map -> totSize = keySize + valSize + 1;
map -> table = _new(map -> cap * map -> totSize);
memset(map -> table, 0, map -> cap * map -> totSize);
return map;
}
void inplace_linear_hash_map_clear(inplace_linear_hash_map_t* map){
memset(map -> table, 0, map -> cap * map -> totSize);
map -> size = 0;
}
void inplace_linear_hash_map_delete(inplace_linear_hash_map_t* map){
_delete(map -> table);
_delete(map);
}
void inplace_linear_hash_map_swap(inplace_linear_hash_map_t* A, inplace_linear_hash_map_t* B){
inplace_linear_hash_map_t C = *A;
*A = *B;
*B = C;
}
int inplace_linear_hash_map_contains(inplace_linear_hash_map_t* map, void* key){
return *_inplace_linear_hash_map_get_label_at(map, _inplace_linear_hash_map_search_for(map, key, 1)) == 2;
}
int inplace_linear_hash_map_is_empty(inplace_linear_hash_map_t* map){
return map -> size == 0;
}
int inplace_linear_hash_map_get_size(inplace_linear_hash_map_t* map){
return map -> size;
}
int inplace_linear_hash_map_get_capacity(inplace_linear_hash_map_t* map){
return map -> cap;
}
void* inplace_linear_hash_map_get_value_at(inplace_linear_hash_map_t* map, void* key){
_inplace_linear_hash_map_calibrate(map);
int poz = _inplace_linear_hash_map_search_for(map, key, 1);
if (*_inplace_linear_hash_map_get_label_at(map, poz) != 2)
return NULL;
return _inplace_linear_hash_map_get_value_at(map, poz);
}
void inplace_linear_hash_map_set_value_at(inplace_linear_hash_map_t* map, void* key, void* val){
int poz = _inplace_linear_hash_map_search_for(map, key, 1);
if (*_inplace_linear_hash_map_get_label_at(map, poz) != 2){
map -> size++;
_inplace_linear_hash_map_set_key_at(map, poz, key);
_inplace_linear_hash_map_set_value_at(map, poz, val);
_inplace_linear_hash_map_set_label_at(map, poz, 2);
} else
_inplace_linear_hash_map_set_value_at(map, poz, val);
}
void inplace_linear_hash_map_insert(inplace_linear_hash_map_t* map, void* key, void* val){
inplace_linear_hash_map_set_value_at(map, key, val);
}
void inplace_linear_hash_map_erase(inplace_linear_hash_map_t* map, void* key){
int poz = _inplace_linear_hash_map_search_for(map, key, 1);
if (*_inplace_linear_hash_map_get_label_at(map, poz) == 2){
map -> size--;
_inplace_linear_hash_map_set_label_at(map, poz, 1);
}
}
void inplace_linear_hash_map_iterate(inplace_linear_hash_map_t* map, void (*iterate)(void*, void*, void*), void* context){
int i;
for (i = 0 ; i < map -> cap ; i++)
if (*_inplace_linear_hash_map_get_label_at(map, i) == 2)
iterate(_inplace_linear_hash_map_get_key_at(map, i), _inplace_linear_hash_map_get_value_at(map, i), context);
}
///DISJOINT SET
typedef struct{
int size, cap;
int* rank;
int* parent;
void* map;
void (*mapInsert)(void*, void*, void*);
void* (*mapValue)(void*, void*);
} disjoint_data_set_t;
void _disjoint_data_set_add_to_reverseIndex(void* key, void* val, void* context){
void** reverseIndex = context;
reverseIndex[*(int*)val] = key;
}
int _disjoint_data_set_get_index_of(disjoint_data_set_t* forest, void* key){
return *(int*)inplace_linear_hash_map_get_value_at(forest -> map, key);
}
int _disjoint_data_set_get_father(int* T, int x){
if (T[x] == x)
return x;
return T[x] = _disjoint_data_set_get_father(T, T[x]);
}
void* disjoint_data_set_new(int startCap, int keySize){
disjoint_data_set_t* forest = _new( sizeof(disjoint_data_set_t) );
forest -> size = 0;
forest -> cap = startCap;
forest -> rank = _new(startCap * sizeof(int));
forest -> parent = _new(startCap * sizeof(int));
forest -> map = inplace_linear_hash_map_new(startCap << 1, keySize, 4);
return forest;
}
void disjoint_data_set_insert(disjoint_data_set_t* forest, void* key){
if (inplace_linear_hash_map_contains(forest -> map, key))
return;
if (forest -> size == forest -> cap){
forest -> cap <<= 1;
if (forest -> cap == 0) forest -> cap = 1;
forest -> rank = _realloc(forest -> rank, forest -> cap * sizeof(int));
forest -> parent = _realloc(forest -> parent, forest -> cap * sizeof(int));
}
forest -> parent[forest -> size] = forest -> size;
forest -> rank[forest -> size] = 1;
inplace_linear_hash_map_insert(forest -> map, key, &(forest -> size));
forest -> size++;
}
int disjoint_data_set_get_set_index(disjoint_data_set_t* forest, void* key){
return _disjoint_data_set_get_father(forest -> parent, _disjoint_data_set_get_index_of(forest, key));
}
int disjoint_data_set_same_set(disjoint_data_set_t* forest, void* firstKey, void* secondKey){
return disjoint_data_set_get_set_index(forest, firstKey) == disjoint_data_set_get_set_index(forest, secondKey);
}
void disjoint_data_set_merge(disjoint_data_set_t* forest, void* firstKey, void* secondKey){
int *T = forest -> parent, *D = forest -> rank;
int x = _disjoint_data_set_get_index_of(forest, firstKey);
int y = _disjoint_data_set_get_index_of(forest, secondKey);
x = _disjoint_data_set_get_father(T, x);
y = _disjoint_data_set_get_father(T, y);
if (x == y)
return;
if (D[x] < D[y]){
T[x] = y;
D[y] += D[x];
} else {
T[y] = x;
D[x] += D[y];
}
}
///ACTUAL PROGRAM
const char feedback[2][10] = {"NU\n", "DA\n"};
void eval(const char* fin, const char* fout){
FILE* in = fopen(fin, "r");
FILE* out = fopen(fout, "w");
void* forest = disjoint_data_set_new(0, 4);
int n, times, tip, x, y;
fscanf(in, "%d%d", &n, ×);
int i;
for (i = 1 ; i <= n ; i++)
disjoint_data_set_insert(forest, &i);
while (times--){
fscanf(in, "%d%d%d", &tip, &x, &y);
if (tip == 1)
disjoint_data_set_merge(forest, &x, &y);
else
fprintf(out, feedback[ disjoint_data_set_same_set(forest, &x, &y) ] );
}
fclose(in);
fclose(out);
}
int main(){
eval("disjoint.in", "disjoint.out");
return 0;
}