[C] Union find solution
I first tried using graph implemented as adjacency matrix and performed depth first search using stack. This worked for 74/100 test cases but exceeded time limi
I first tried using graph implemented as adjacency matrix and performed depth first search using stack. This worked for 74/100 test cases but exceeded time limit for the 75th case. \n\nI referred to [Algorithms made easy - @khushbugupta \'s video](https://www.youtube.com/watch?v=2mva2YRgrW8) on union-find and implemented the same in C.\n\n```\nint find_max(int* arr, int ASize)\n{\n    int max = arr[0];\n    for(int i = 1; i < ASize; ++i)\n    {\n        max = arr[i] > max ? arr[i] : max;\n    }\n    return max;\n}\n\nint find(int* arr, int x)\n{\n    if(arr[x] != x)\n    {\n        arr[x] = find(arr, arr[x]);\n    }\n    return arr[x];\n}\n\nvoid unionn(int* arr, int x, int y)\n{\n    arr[find(arr, x)] = arr[find(arr, y)];\n}\n\nint maximum(int x, int y)\n{\n    return x > y ? x : y;\n}\n\nint largestComponentSize(int* A, int ASize)\n{\n    int max = find_max(A, ASize);\n    int* relationships = (int*)malloc((max+1) * sizeof(int));\n    for(int i = 0; i < max+1; ++i)\n    {\n        relationships[i] = i;\n    }\n    int num;\n    for(int i = 0; i < ASize; ++i)\n    {\n        num = A[i];\n        for(int j = 2; j <= sqrt(num); ++j)\n        {\n            if(num % j == 0)\n            {\n                unionn(relationships, num, j);\n                unionn(relationships, num, num/j);\n            }\n        }\n    }\n    //the value at res_dict[i] denotes the number of nodes which have relationship with i\n    int* res_dict = (int*)calloc(max+1, sizeof(int));\n    int prime_num;\n    int res = 0;\n    for(int i = 0; i < ASize; ++i)\n    {\n        prime_num = find(relationships, A[i]);\n        ++res_dict[prime_num];\n        res = maximum(res, res_dict[prime_num]);\n    }\n    return res;\n}\n\n\n\n//OWN ATTEMPT : EXCEEDED TIME LIMIT AFTER BEING SUCCESSFUL FOR 74/100 TEST CASES\n/*int gcd(int a, int b) \n{ \n    if (a == 0) \n        return b; \n    return gcd(b%a, a); \n}\n\n\nint** construct_graph(int* A, int ASize) //construct a graph (adjacency matrix) with the given constraints\n{\n    int** graph = (int**)malloc(ASize * sizeof(int*));\n    for(int i = 0; i < ASize; ++i)\n    {\n        graph[i] = (int*)malloc(ASize * sizeof(int));\n    }\n    for(int i = 0; i < ASize; ++i)\n    {\n        for(int j = i+1; j < ASize; ++j)\n        {\n            if(gcd(A[i], A[j]) != 1)\n            {\n                graph[i][j] = graph[j][i] = 1;\n            }\n            else\n            {\n                graph[i][j] = graph[j][i] = 0;\n            }\n        }\n    }\n    return graph;\n}\n\n\nstruct stack{\n    int* arr;\n    int top;\n    int capacity;\n};\n\ntypedef struct stack stack;\n\nstack* init_stack(int capacity)\n{\n    stack* st = (stack*)malloc(sizeof(stack));\n    st -> top = -1;\n    st -> capacity = capacity;\n    st -> arr = (int*)malloc(capacity * sizeof(int));\n    return st;\n}\n\nint is_Full(stack* st)\n{\n    return st -> top == st -> capacity -1;\n}\n\nint is_Empty(stack* st)\n{\n    return st -> top == -1;\n}\n\nvoid push(stack* st, int key)\n{\n    if(!is_Full(st))\n        st -> arr[++st -> top] = key;\n}\n\nint pop(stack* st)\n{\n    if(!is_Empty(st))\n        return st -> arr[st->top--];\n    return -1;\n}\n\nint find_length(int* A, int ASize, int** graph, int key_index, int* visited)\n{\n    int count = 0;\n    stack* st = init_stack(ASize);\n    int* inStack = (int*)calloc(ASize, sizeof(int));\n    int node_index = key_index;\n    push(st, node_index);\n    inStack[node_index] = 1;\n    while(!is_Empty(st))\n    {\n        node_index = pop(st);\n        ++count;\n        visited[node_index] = 1;\n        for(int i = 0; i < ASize; ++i)\n        {\n            if(graph[node_index][i] && visited[i] == 0 && !inStack[i])\n            {\n                push(st, i);\n                inStack[i] = 1;\n            }\n        }\n    }\n    return count;\n}\n\nint largestComponentSize(int* A, int ASize){\n    int** graph = construct_graph(A, ASize);\n    int* visited = (int*)calloc(ASize, sizeof(int));\n    int res = 0;\n    int sub_graph_length;\n    for(int i = 0; i < ASize; ++i)\n    {\n        if(visited[i] == 0)\n        {\n            sub_graph_length = find_length(A, ASize, graph, i, visited);\n            if(sub_graph_length > res)\n                res = sub_graph_length;\n        }\n    }\n    return res;\n}*/\n```
[]