CareerCup

Use Kruskal's to find out the MST. Use a DSU to maintain already connected nodes. Initialize DSU with already built nodes.

Actually an int is not guaranteed to be 4 bytes on all platforms, so we can ise stdint.h's uint32_t to get sure 4bytes width

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

uint32_t str_to_int(char *in) {
    if (!in)
        return 0;
    uint32_t ret = 0;
    int i = 0;
    while (i < 4) {
        ret |= (in[i] << 8 * i++);
    }
    return ret;
}

void int_to_str(uint32_t in, char *out) {
    if (!out)
        return;
    int i = 0;
    while (i < 4) {
        out[i++] = in >> 8 * i;
    }
}

int main(int argc, char **argv) {
    char *in = "ABxy";

    uint32_t int_out = str_to_int(in);
    printf("%x\n", int_out);

    char *out = malloc(4);
    int_to_str(int_out, out);
    printf("%s\n", out);

    free(out);
    return 0;
}

Here's and O(N) solution with constant space

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define forup(i,a,b) for(i=(a); i<(b); ++i)
#define fordn(i,a,b) for(i=(a); i>(b); --i)
#define rep(i,a) for(i=0; i<(a); ++i)

#define gi(x) scanf("%d",&x)
#define gl(x) cin>>x
#define gd(x) scanf("%lf",&x)
#define gs(x) scanf(" %s",x)

#define fs first
#define sc second

#define pb push_back
#define mp make_pair

const int inf=numeric_limits<int>::max();
const LL linf=numeric_limits<LL>::max();

const int max_n=100;

char a[max_n], b[max_n];
int fe[26], fo[26], la, lb, i;

int main() {
    scanf("%s", a);
    scanf("%s", b);
    la = strlen(a);
    lb = strlen(b);
    if(la != lb){
        cout << "NO";
        return 0;
    }
    // Save frequencies of even and odd places +f for each char
    rep(i, la){
        if(i%2) fo[a[i]-'a']++;
        else fe[a[i]-'a']++;
    }
    // -f for each char
    rep(i, lb){
        if(i%2) fo[b[i]-'a']--;
        else fe[b[i]-'a']--;
    }
    // should be same for both a and b if fe and fo are 0
    rep(i, 26){
        if(fe[i]!=0 || fo[i]!=0){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

A simple solution involving Os in same row/column as a connected in a graph. dfs to find the number of connected components. Can be written better with iterative dfs maybe?

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define forup(i,a,b) for(i=(a); i<(b); ++i)
#define fordn(i,a,b) for(i=(a); i>(b); --i)
#define rep(i,a) for(i=0; i<(a); ++i)

#define gi(x) scanf("%d",&x)
#define gl(x) cin>>x
#define gd(x) scanf("%lf",&x)
#define gs(x) scanf(" %s",x)

#define fs first
#define sc second

#define pb push_back
#define mp make_pair

const int inf=numeric_limits<int>::max();
const LL linf=numeric_limits<LL>::max();

const int max_n=100;

int n;

char arr[max_n][max_n], com[max_n][max_n];

void dfs(int y, int x, int comp){
    int i;
    com[y][x] = comp;
    forup(i, y+1, n){
        if(arr[i][x] == 'O' && !com[i][x])
            dfs(i, x, comp);
    }
    forup(i, x+1, n){
        if(arr[y][i] == 'O' && !com[y][i])
            dfs(y, i, comp);
    }
}

int main() {
    int i, j, k, comp;
    gi(n);
    rep(i, n){
            scanf("%s", arr[i]);
    }

    comp = 0;

    rep(i, n){
        rep(j, n){
            if(arr[i][j] == 'O' && !com[i][j])
                dfs(i, j, comp++);
        }
    }
    printf("%d\n", --comp);
    return 0;
}