Блог пользователя Not_MainCharacter

AtCoder232 Problem C is sus ?
Автор Not_MainCharacter, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +49 Проголосовать: не нравится

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:

→ Ответить
»
3 года назад, # |
← Rev. 4   Проголосовать: нравится +22 Проголосовать: не нравится

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! =))

→ Ответить