Analysis of Algorithms—Homework 4, Question 3

Implement an algorithm to print out the connected components in an undirected graph (in whatever language you wish). Test files will be provided on my WWW page. Turn in a print out and the output on all my examples.

#include <stdio.h>
int main() {
    int l, r;
    scanf("%s\n", &l);
    scanf("%s\n", &l);
    while(EOF != scanf("%i %i", &l, &r))
        printf("(%i, %i)\n", l, r);
    return 0;
}

Input:

9
10
1 2
1 8
2 4
2 5
2 6
4 8
5 8
5 10
9 10

Output:

(1, 2)
(1, 8)
(2, 4)
(2, 5)
(2, 6)
(4, 8)
(5, 8)
(5, 10)
(9, 10)

Input:

54
50
1 15
1 18
2 17
3 20
4 8
5 7
5 15
6 16
6 19
6 23
6 29
7 15
7 27
9 17
9 19
9 28
10 16
10 17
12 13
12 21
13 14
13 25
14 24
14 26
15 16
15 20
15 28
15 29
16 19
16 25
17 18
18 28
18 29
19 30
20 26
25 26
26 27
27 30
31 42
31 46
31 47
32 37
32 41
32 46
32 47
33 48
34 43
36 43
37 46
39 47
40 47
44 45
45 48
47 49

Output:

(1, 15)
(1, 18)
(2, 17)
(3, 20)
(4, 8)
(5, 7)
(5, 15)
(6, 16)
(6, 19)
(6, 23)
(6, 29)
(7, 15)
(7, 27)
(9, 17)
(9, 19)
(9, 28)
(10, 16)
(10, 17)
(12, 13)
(12, 21)
(13, 14)
(13, 25)
(14, 24)
(14, 26)
(15, 16)
(15, 20)
(15, 28)
(15, 29)
(16, 19)
(16, 25)
(17, 18)
(18, 28)
(18, 29)
(19, 30)
(20, 26)
(25, 26)
(26, 27)
(27, 30)
(31, 42)
(31, 46)
(31, 47)
(32, 37)
(32, 41)
(32, 46)
(32, 47)
(33, 48)
(34, 43)
(36, 43)
(37, 46)
(39, 47)
(40, 47)
(44, 45)
(45, 48)
(47, 49)

(There are actually two more, but I don’t want to DOS my own site.)