C, Union-Find 100%
IntuitionUse union-find, use the bit masks to store the propertiesComplexity

Time complexity:
O(n2)


Space complexity:
O(n)

Code
# Intuition
Use union-find, use the bit masks to store the properties

# Complexity
- Time complexity:
$$O(n^2)$$

- Space complexity:
$$O(n)$$

# Code
```c []

/* hold bits for ~100 properties 2x64 bit numbers*/
typedef struct {
   /* tree of sets, set size, link to parent */
   unsigned char size, parent;
   unsigned long long props[2];
} setData;

/* union find instance */
typedef struct {
    unsigned char nSets; /* numbers of disjoint sets*/
    setData* data; /* Data for each set member */
} unionFind;


/* efficient bit count for 64 bit numbers */
unsigned char bitCount(unsigned long data) {
    data = (data & 0x5555555555555555) + ((data & 0xAAAAAAAAAAAAAAAA) >> 1);
    data = (data & 0x3333333333333333) + ((data & 0xCCCCCCCCCCCCCCCC) >> 2);
    data = (data & 0x0F0F0F0F0F0F0F0F) + ((data & 0xF0F0F0F0F0F0F0F0) >> 4);
    data = (data & 0x00FF00FF00FF00FF) + ((data & 0xFF00FF00FF00FF00) >> 8);
    data = (data & 0x0000FFFF0000FFFF) + ((data & 0xFFFF0000FFFF0000) >> 16);
    data = (data & 0x00000000FFFFFFFF) + ((data & 0xFFFFFFFF00000000) >> 32);
    return data;
}

/* finding the set by its member, returnse the set id */
unsigned char getSet(unionFind* pufData, unsigned char x) {
    unsigned char curX = x;
    unsigned char prevX = pufData->data[curX].parent;

    /* traverse to the parent */
    while (prevX != curX) {
        curX = prevX;
        prevX = pufData->data[curX].parent;
    }

    /* walk again to compress the path */
    curX = pufData->data[x].parent;
    while (curX != prevX) {
        pufData->data[x].parent = prevX;
        x = curX;
        curX = pufData->data[x].parent;
    }

    return prevX;
}

/* join two sets, returns 1 if the join took place or 0 x and y are already in the same set */
unsigned char unionSets(unionFind* pufData, unsigned char x, unsigned char y) {
    x = getSet(pufData, x);
    y = getSet(pufData, y);
    if (x == y) return 0;

    /* merge smaller to larger */
    if (pufData->data[x].size >= pufData->data[y].size) {
        pufData->data[x].size += pufData->data[y].size;
        pufData->data[y].parent = x;
    } else {
        pufData->data[y].size += pufData->data[x].size;
        pufData->data[x].parent = y;
    }
    /* reduce the current number of sets*/
    --pufData->nSets;
    return 1;
}

/* Allocate to "size" sets */
void allocateUFData(unionFind* puf, int size) {
    puf->nSets = size;
    puf->data = malloc(size * sizeof(setData));
}

/* deallocate tje UF structure */
void deallocateUFData(unionFind* puf) {
    free(puf->data);
}
int numberOfComponents(int** properties, int propertiesSize, int* propertiesColSize, int k) {
    unionFind ufData;
    allocateUFData(&ufData, propertiesSize);

    /* Populate the UF structure */
    setData* tempData = ufData.data;
    int** curProperties = properties;
    int* curPropColSize = propertiesColSize;
    unsigned char x, y;

    
    for (x = 0; x < propertiesSize; ++x, ++tempData, ++curProperties, ++curPropColSize) {
        /* each set is size 1 at start*/
        tempData->size = 1;
        /* properties set to 0 */
        tempData->props[0] = 0UL;
        tempData->props[1] = 0UL;

        tempData->parent = x; /* each set is unique at start 0..n-1 */

        /* Collect properties into bits */
        int* curProperty = *curProperties;
        for (y = 0; y < *curPropColSize; ++y, ++curProperty) {
            /* under 64 to lower part, over 64 to higher part */
            if (*curProperty < 64) {
                tempData->props[0] |= (1UL << *curProperty);
            } else {
                tempData->props[1] |= (1UL << (*curProperty - 64));
            }
        }

    }

   /* run the edge check between every pair or the vertices: x,y */
    setData* xData = ufData.data + 1;
    for (x = 1; x < propertiesSize; ++x, ++xData) {
        setData* yData = ufData.data;
        for (y = 0; y < x; ++y, ++yData) {
            unsigned char flagCount = bitCount(xData->props[0] & yData->props[0]);
            if (flagCount >= k || (flagCount + bitCount(xData->props[1] & yData->props[1])) >= k) {
                if (unionSets(&ufData, x, y) == 1) {
                    if (ufData.nSets == 1) {
                        /* if already down to 1 set, stop and return 1 */
                        deallocateUFData(&ufData);
                        return 1;
                    }
                }
            }
        }
    }

    deallocateUFData(&ufData);
    return ufData.nSets;
}
```
['C']