Cod sursa(job #2605917)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 26 aprilie 2020 12:44:44
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>

int Find(int x, int *c) {
    int y = x, t;
    while(y != c[y])
        y = c[y];

    while(x != y) {
        t = c[x];
        c[x] = y;
        x = t;
    }

    return x;
}

void Unite(int x, int y, int *c) {
    x = Find(x, c);
    y = Find(y, c);
    c[y] = x;
}

int main() {

    int N, M, *c, type, A, B;
    FILE *input = fopen("disjoint.in", "r");
    FILE *output = fopen("disjoint.out", "w");

    fscanf(input, "%d%d", &N, &M);

    c = (int *) calloc(N + 1, sizeof(int));
    for(int i = 1; i <= N; i++)
        c[i] = i;

    for(int i = 1; i <= M; i++) {
        fscanf(input, "%d %d %d", &type, &A, &B);
        if(type == 1) {
            if((A = Find(A, c)) != (B = Find(B, c)))
                Unite(A, B, c);
        } else {
            if(Find(A, c) == Find(B, c)) {
                fprintf(output, "DA\n");
            } else {
                fprintf(output, "NU\n");
            }
        }
    }

    free(c);
    fclose(input);
    fclose(output);

    return 0;
}