2. Input: 1) A number n denoting the number of computers in a network (labelled

Question

2. Input: 1) A number n denoting the number of computers in a network (labelled from 0 to n-1) 2) A list of computers that are connected to each other. 3) A number denoting a computer that just got infected with a virus. For example, below there are 10 computers (named 0-9). Computer 3 is connected to computer 2, etc. Finally, the last line states that computer 1 has just become infected. 10 3 2 7 8 12 3 9 9 1 01 6 7 8 6 Output: List all computers that will be infected with the virus, ie, all computers that can be reached from computer 1. In this case, the answer is 1, 0, 9, 2, 3 Hints: This is similar to a problem you've solved in the past.

Explanation / Answer

We used a Depth first search algorithm to find the connectivity between computers :

#include <stdio.h>
int main(){
        int N,i,**adj,*visited,a,b,infected,j; // Initializing and declaring the variables
        scanf("%d",&N);                        //Reading the number of nodes
        visited = (int *)malloc(N*sizeof(int));     // Assigning an address to a pointer variables.
        adj = (int **)malloc((N+1) * sizeof(int *));
    for (i=0; i<=N; i++)
        adj[i] = (int *)malloc((N+1) * sizeof(int));
        for(i=0; i<N; i++){
         for(j=0; j<N; j++)
               adj[i][j] = 0;                         //Initializing the adjacent matrix with zeroes
     }
        while((scanf("%d",&a) == 1) && (scanf("%d",&b) == 1)){     // reading the inputs
        //arr[i][0] = a;
         //arr[i][1] = b;
         adj[a][b] = 1;                                          //assigning the adjacency matrix if theres is a connection
         adj[b][a] = 1;
    }
        infected = a;                                           //assigning the infected computer
        for(i=0; i<N; i++){
            visited[i] = 0;                                    //Initializing visited array with zeros
        }
        DFS(adj,visited,N,infected);                           //Using DFS to find the connectivity
        for(i=0; i<N; i++){
            if(visited[i] == 1)                               //printing all connected components(infected computers)
                printf("%d ",i);
        }
}

int DFS(int **adj,int *visited,int N,int infected) // We used Depth first search algorith to find the connected computers
{
    int *stack,top = 0,i,j,top1=0,temp;
    stack = (int *)malloc(N*sizeof(int));
    stack[top] = infected;
    i = top;
    top1 = top;
    while(i>=0){
        //printf("stack %d",stack[i]);
        temp = stack[i];
        for(j=0; j<N; j++){
            //printf("%d%d ",temp,j);
           if(adj[temp][j] == 1 && (visited[j] == 0)){

               visited[j] = 1;
              visited[stack[i]] = 1;
              stack[top++] = j;
            // printf("%d%d ",stack[i],j);
            }
        }
        top--;
        i = top;
        //printf(" ");
    }
}

output :

deepak@deepak-ThinkPad-SL:~$ gcc chg.c
deepak@deepak-ThinkPad-SL:~$ ./a.out
10
3 2
7 8
1 2
3 9
9 1
0 1
6 7
8 6   
1
0 1 2 3 9 deepak@deepak-ThinkPad-SL:~$

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.