CODEWITHSUNDEEP
javapythonalgorithmgraph
sathariel
sathariel

Reputation: 19

Need help to create algorithm that will sort people into groups based by their opinion

I have a following problem

input looks like this:

agree 1 2
disagree 2 3
? 1 2
? 1 3
agree 1 3
? 4 5
agree 0 5

and so on. Numbers represent people (numbered from 0 to n). agree means that those two people have the same opinion(i don't know which though, if positive or negative, i just know it's the same). disagree means they have different opinions. ? is a question that the program has to answer and that is, if those two people have the same opinion or not.

output for this particular input should look like this :

yes
no
error
don't know

yes is because the first question asked was if 1 and 2 have the same opinion which they have based on the first input line. no is because 1 and 3 have different opinions, because we could see that 1 agrees with 2 and 2 disagrees with 3 so 1 has to disagree with 3. error is because then we got input that 1 agrees with 3 which we know is a lie so we print out error. don't know is because the last question was about 4 and 5 who weren't mentioned before so we don't know their opinions.

So my idea was to create a class Person and give them attributes : number and color (for opinion) but then i realized this won't work in cases when i will get not connected groups for example 1 2 agree, 4 5 agree and then i would get question if 2 4 agree, i shouldn't know the answer but they would have the same color..

My question is, if you could help me figure out the best way to store the information about opinions for each person, preferably in Java, or Python.

Upvotes: 0

Views: 98

Answers (2)

Noctua
Noctua

Reputation: 5218

The cleanest way to solve this is probably using a variation of Union - Find algorithm, which uses a data structure called disjoint-set data structure. If you include in each set a "colour" as root, you can easily find the colour a person (number) belongs to. You would have to add some extra checks when merging to sets, so you can print your "error".

If speed is not important, it's probably easier to take the naive approach and skip collapsing the union chains.

Upvotes: 0

fabian
fabian

Reputation: 82491

Use a disjoint-set data structure to get the connected components of the graph induced by the agrees.

This results in a partition of the vertices (=persons) P = {P_1, P_2, ..., P_n}

Then consider the graph following graph:

G = (P, {(A, B) ∈ P² | ∃ a ∈ A, b ∈ B: disagree(a, b)})

I.e. 2 partitions are connected in the new Graph, iff there are 2 vertices among there nodes that disagree.

Now you can get the results as follows:

  • don't know if the persons are not inside vertices in G that belong to a connected component of G
  • otherwise 2-color the connected component containing both persons in G. The result is:
    • error if there are any 2 vertices in the connected component, that contain persons that disagree or if there is no 2 coloring of the connected component
    • yes if not error and the vertices containing the persons have the same color
    • no otherwise

Upvotes: 1

Related Questions