You are not logged in. Please login at www.codechef.com to post your questions!

×

GRAPHCT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

It can be shown that G has a cycle of length 5 as a minor iff G has a cycle of length >= 5 in it. So we wish to count biconnected graphs having no cycle of length >= 5.

We start by working out a few special cases for n <= 4. Now, first we show that any biconnected graph having n >= 5 vertices has a cycle of length atleast 4. Consider any nodes u and v which are not connected. Since there are atleast 2 disjoint paths between u and v (each of length >= 2), we can combine them to form a cycle of length >= 4. Hence, the only possibility is that for all u,v there is an edge between then. But in that case, the graph is a clique and has a cycle of length >= 4. Thus, all biconnected components having >= 5 vertices have a cycle.

Now we can use an ear decomposition of two connected graphs. The result basically says that we can start off with any cycle in G, and form the graph progressively by adding maximal paths (ears) to G. So we start off with a cycle having 4 nodes (one surely exists, as we have seen above). Now analysing a few cases reveals that the only way to add ears to G are between 1 diagonal, and each ear should have length exactly 2. In all other cases, we get a cycle of length >= 5. Thus, G looks like this : there are two nodes u and v, with n - 2 disjoint paths of length 2 between them. We can optionally add a direct edge between u and v if needed. Thus, the total number of edges in G are either 2 * (n-2) or 2 * (n-2) + 1. We can choose u and v in ncr(n,2) ways. This gives us the following result :

if n = 1, output 1 if m = 1, else 0
if n = 2, output 1 if m = 1, else 0
if n = 3, output 1 if m = 3, else 0
if n = 4, output 3 if m = 4. If m = 6 output 1, else if m = 5 output 6. else output 0
for n >= 5, output n * (n-1)/2 if m = 2 * (n-2) or m = 2 * (n-2) + 1. else output 0.

This question is marked "community wiki".

asked 28 Nov '12, 15:49

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 35%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,683
×1,343
×6
×1

question asked: 28 Nov '12, 15:49

question was seen: 5,021 times

last updated: 28 Nov '12, 15:49