Not_MainCharacter's blog

AtCoder232 Problem C is sus ?
By Not_MainCharacter, history, 3 years ago, In English

For the problem Graph-Isomorphism the Editorial provided was BruteForce and I checked some other coders' solutions, they were the same.
But what the problem saying is that check if both are Isomorphism or not
And as per the constraint we know the number of vertices and the edges for both parties is same, So can't we just check if they have a similar Degree Sequence or not ?
I tried solving using Degree Sequence logic but it was failed in just 1 test case.
I want to know if Degree Sequence logic can't be applied then why? I am confused, Please Kindly anyone explain.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +49 Vote: I do not like it

If two graphs are isomorphic then they have the same degree sequence.

But just because two graphs have the same degree sequence does not mean they are isomorphic.

Example:

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +22 Vote: I do not like it

As far as I understand, we cannot use degree, because graphs can be disconnected:

Here, graphs $$$G_1$$$ and $$$G_2$$$ are not isomorphic despite the fact that all the vertices in both of the graphs have degree $$$2$$$.

Maybe there is a case when two graphs could both be connected and have the same degrees in each vertex and still be not isomorphic, but I couldn't come up with an example.

Strangely, I didn't see -is-this-fft- comment, before I posted mine.. Looks like there is a bug in codeforces.

And I cannot delete my comment! Help! =))

→ Reply