# Answer to Question #60886 in C for maxx

Question #60886

In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee.

Expert's answer

#include <stdio.h>

/*

*If we imagine that students are vertexes of graph and their friendships are edges,

*we can solve this task checking is this graph bipartite or not

*

*We can colve it using depth-first search

*/

int g[100][100]; //graph adjacency matrix

int used[100];

int is_ok = 1; //value for checking graph, 'is_ok' = 1 - it is a bipartite graph, otherwise - not bipartite

int n; // number of students

void dfs (int v, int colour) { //depth-first search algorithm

if (colour == 1)

used[v] = 2;

else

used[v] = 1;

int i;

for (i = 0; i < n; i++)

if (g[v][i] == 1) { //if there is an edge

if (used[i] == used[v]) //this graph is not bipartite

is_ok = 0;

if (!used[i])

dfs (i, used[v]);

}

}

int main () {

int i, j; //iterators

printf ("Enter number of students: ");

scanf ("%d" ,&n); //reading number of students

printf ("Enter matrix of student friendship (1 - friendship exist, 0 - not exist)\n");

for (i = 0; i < n; i++) { //reading all friendships

for (j = 0; j < n; j++)

scanf ("%d", &g[i][j]);

used[i] = 0;

}

for (i = 0; i < n; i++) //checking graph

if (!used[i]) {

dfs (i, 1);

if (!is_ok) {

printf ("Can not identify two groups of people such that a person in one group must not be a friend to any other in the same group\n");

return 0;

}

}

printf ("Lists\n"); //printing listss

//printing first list

printf ("1: ");

for (i = 0; i < n; i++)

if (used[i] == 1)

printf ("%d ", i + 1);

printf ("\n");

//printing second list

printf ("2: ");

for (i = 0; i < n; i++)

if (used[i] == 2)

printf ("%d ", i + 1);

printf ("\n");

return 0;

}

/*

*If we imagine that students are vertexes of graph and their friendships are edges,

*we can solve this task checking is this graph bipartite or not

*

*We can colve it using depth-first search

*/

int g[100][100]; //graph adjacency matrix

int used[100];

int is_ok = 1; //value for checking graph, 'is_ok' = 1 - it is a bipartite graph, otherwise - not bipartite

int n; // number of students

void dfs (int v, int colour) { //depth-first search algorithm

if (colour == 1)

used[v] = 2;

else

used[v] = 1;

int i;

for (i = 0; i < n; i++)

if (g[v][i] == 1) { //if there is an edge

if (used[i] == used[v]) //this graph is not bipartite

is_ok = 0;

if (!used[i])

dfs (i, used[v]);

}

}

int main () {

int i, j; //iterators

printf ("Enter number of students: ");

scanf ("%d" ,&n); //reading number of students

printf ("Enter matrix of student friendship (1 - friendship exist, 0 - not exist)\n");

for (i = 0; i < n; i++) { //reading all friendships

for (j = 0; j < n; j++)

scanf ("%d", &g[i][j]);

used[i] = 0;

}

for (i = 0; i < n; i++) //checking graph

if (!used[i]) {

dfs (i, 1);

if (!is_ok) {

printf ("Can not identify two groups of people such that a person in one group must not be a friend to any other in the same group\n");

return 0;

}

}

printf ("Lists\n"); //printing listss

//printing first list

printf ("1: ");

for (i = 0; i < n; i++)

if (used[i] == 1)

printf ("%d ", i + 1);

printf ("\n");

//printing second list

printf ("2: ");

for (i = 0; i < n; i++)

if (used[i] == 2)

printf ("%d ", i + 1);

printf ("\n");

return 0;

}

Need a fast expert's response?

Submit orderand get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

## Comments

## Leave a comment