Find Maximum Chords

.gitignore

out.txt
a.out

500.in

500
38 219
238 437
355 297
365 285
450 112
353 100
142 281
37 421
445 497
180 476
391 155
406 457
323 381
240 225
278 446
90 340
87 407
237 111
117 456
367 33
378 223
387 97
84 212
78 66
129 404
279 5
388 149
329 176
331 264
114 136
428 102
152 337
356 98
272 213
183 203
260 442
247 375
371 4
173 319
239 186
304 23
335 393
20 74
483 461
124 65
69 330
167 236
249 119
227 200
422 274
311 62
191 50
120 334
468 24
77 46
31 458
30 134
81 435
160 314
27 94
268 244
324 21
307 296
226 263
140 47
80 328
113 259
243 494
361 133
72 151
254 470
19 474
321 322
410 452
248 156
411 475
436 255
447 354
493 341
204 316
56 1
427 214
51 83
174 346
14 299
165 60
360 86
350 22
233 455
257 275
141 440
177 116
122 147
132 195
306 175
379 53
482 162
201 245
91 359
313 294
154 18
283 208
405 477
25 130
252 372
466 61
157 489
110 75
364 426
193 397
415 89
492 396
479 478
198 258
143 383
303 26
9 190
2 251
384 35
54 282
298 137
115 126
17 232
32 465
88 453
29 267
394 357
93 207
412 63
336 301
402 135
71 8
192 40
109 498
234 121
370 101
449 222
36 179
211 487
339 199
187 351
79 443
92 16
291 392
108 184
403 451
432 105
194 67
242 205
295 484
6 460
96 42
400 48
159 273
395 308
221 419
99 382
181 64
462 270
420 266
70 327
158 287
39 284
333 344
325 206
433 125
269 349
464 417
471 197
163 490
377 413
104 399
302 164
161 166
12 189
290 277
472 326
73 488
150 57
300 3
7 288
369 107
15 347
59 172
246 352
13 241
423 280
320 131
343 429
153 276
229 373
169 444
209 467
231 293
10 463
441 55
28 358
292 469
315 76
49 127
182 448
34 210
118 262
144 366
499 188
318 215
309 0
224 496
106 332
473 216
256 480
58 265
202 439
380 385
368 68
389 185
41 363
430 44
52 376
217 11
459 418
485 414
408 434
286 228
170 386
218 271
145 491
438 82
146 178
289 424
338 454
128 43
253 250
401 348
390 220
45 486
342 362
148 495
310 168
138 139
196 123
85 398
481 374
305 425
409 317
95 235
103 261
431 171
416 230
345 312
0

homework.c

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

#define MAX(a, b) a>b?0:1

struct MIS {
    int numOfChords;
    int *chords;
};

void append(struct MIS *tableA, struct MIS *tableB) {
    int flag, index;
    int *tmp = malloc(sizeof(int) * (tableA->numOfChords + tableB->numOfChords) + 1);

    // Append tableA 
    for (flag = 0, index = 0; flag < tableA->numOfChords; flag++, index++)  
        tmp[flag] = tableA->chords[index];

    // Append tableB
    for (flag = flag, index = 0; flag < tableA->numOfChords + tableB->numOfChords; flag++, index++) 
        tmp[flag] = tableB->chords[index];

    tableA->numOfChords += tableB->numOfChords;
    
    free(tableA->chords);
    tableA->chords = tmp;
}

void appendValue(struct MIS *tableA, int value) {
    struct MIS tmp;
    tmp.numOfChords = 1;
    tmp.chords = malloc(sizeof(int));
    tmp.chords[0] = value;

    append(tableA, &tmp);

    free(tmp.chords);
}

struct MIS **findMaxChords(struct MIS **table, int *connectedTable, int n) {
    int i, j;
    int count = 0;

    for (j = 0; j < n; j++) {
        for (i = 0; i <= j; i++) {
            int k = connectedTable[j];

            if (k<i || k>j) 
            {
                append(&table[i][j], &table[i][j-1]);
            }
            else if (k>i && k<j) 
            {
                switch (MAX(table[i][j-1].numOfChords, table[i][k-1].numOfChords + table[k+1][j-1].numOfChords + 1)) {
                    case 0:
                        append(&table[i][j], &table[i][j-1]);
                        break;
                    case 1:
                        appendValue(&table[i][j], k);
                        append(&table[i][j], &table[i][k-1]);
                        append(&table[i][j], &table[k+1][j-1]);
                        break;
                }
            }
            else 
            {
                appendValue(&table[i][j], k);
                append(&table[i][j], &table[i+1][j-1]);
            }
        }
    }
    return table; 
}

// Create table of connected chords
int *createConnectedChords(int *table, int *chords) {
    int i = 0;

    table = malloc(sizeof(table)*chords[0]);    

    for (i = 1; i < chords[0]; i+=2) {
        table[chords[i]] = chords[i+1];
        table[chords[i+1]] = chords[i];
    }

    return table;
}

// Allocate memory to the matrix
struct MIS **createMatrix(struct MIS **table, int *chords) {
    int i, j;
    int n = chords[0];

    // Allocate memory to matrix
    table = malloc(n * sizeof(struct MIS*));

    for (i = 0; i < n; i++) {
        table[i] = malloc(n * sizeof(struct MIS));
        for (j = 0; j < n; j++) {
            table[i][j].numOfChords = 0;
            table[i][j].chords = malloc(0*sizeof(int));
        }
    }

    return table;
}

int *loadFile(const char *path) {
    FILE *fptr = fopen(path, "r");

    if (!fptr) {
        printf("Fail to open file.");
        exit(1);
    }
    
    int n, i;
    int *tmp;

    fscanf(fptr, " %d\n", &n);
    
    tmp = malloc(n*sizeof(int)+1);
    tmp[0] = n;

    for (i=0; i<n/2; i++) {
        int a, b;
        fscanf(fptr, "%d %d\n", &a, &b);
        tmp[i*2+1]=a;
        tmp[i*2+2] = b;
    }


    return tmp;
}

void writeFile(const char *path, struct MIS table, int *connectedTable) {
    int i;
    FILE *fptr = fopen(path, "w");

    if (!fptr) {
        printf("Fail to open file.");
        exit(1);
    }

    fprintf(fptr, "%d\n", table.numOfChords);

    for (i = table.numOfChords-1; i >= 0; i--) {
        int idx = table.chords[i];
        fprintf(fptr, "%d %d\n", idx, connectedTable[idx]);
    }

    fclose(fptr);
}

int main(int argc, char **argv) {
    if (argc != 3) {
        printf("Usage:<Input file> <Output file>\n");
        return 1;
    }
    
    // Declare two dimension matrix
    struct MIS **table;
    int i;
    int *connectedTable;
    int *chords = loadFile(argv[1]);

    table = createMatrix(table, chords);
    connectedTable = createConnectedChords(connectedTable, chords);

    table = findMaxChords(table, connectedTable, chords[0]);

    writeFile(argv[2], table[0][chords[0]-1], connectedTable);
    
    return 0;
}

makefile

run:
	gcc homework.c  && ./a.out 5000.in out.txt && cat out.txt