Write a C program

P1 (40 pts) Assume a graph represents a social network: the vertices are people and the edges are friendship relation between them. Implement a program that does the following:

- reads the graph with input redirection.

- prints the graph to verify it was loaded correctly.

- find the connected components and label them with numbers (starting at 1) and

- print the connected components. In particular print the names of the people in that connected component. You can assume the graph is an undirected graph.

The graph data is given in the order:

- N (number of vertices) - Vertices: N lines each containing one string with a vertex name.

- Edges: A number of lines in format: name1 name 2. The line -1 -1 indicates the end of lines with edges. Files: data1.txt, run1.txt. Save the program in a file called graph.c. Hint: you can adapt the DFS (Depth First Search) algorithm to label connected components.

file data.txt :

10 Sam Thomas Judy Sue Anne Todd Elsa Jay Brad Joe Sam Thomas Sue Anne Elsa Brad Todd Sam Anne Todd Judy Jay -1 -1

sample out put:

run command: $ ./gr1 < data1.txt Program output: Enter number of vertices, N: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1: Enter name1 name2: 0-1 Enter name1 name2: Enter name1 name2: Enter name1 name2: Enter name1 name2: Enter name1 name2: Enter name1 name2: GRAPH: N = 10 0-Sam 1-Thomas 2-Judy 3-Sue 4-Anne 5-Todd 6-Elsa 7-Jay 8-Brad 9-Joe 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Number of groups: 4 Group: 1 Sam Thomas Sue Anne Todd Group: 2 Judy Jay Group: 3 Elsa Brad Group: 4 Joe