10661 - The Perspectographer

Per · Post by **Per** » Sat Jun 12, 2004 2:05 pm

GBY wrote:Finding the number of the largest clique is indeed one way to solve the problem.In this problem you needn't find the largest clique of the whole graph but the one which contains current piece(that's enough).So using loops to count is enough.

I don't understand this. By "number" of the largest clique, do you mean something else than size? In the first test case I posted, the largest clique has size 2, yet the output should be 3.

Shamim: greedy won't work; the problem is NP-complete.

GBY · Post by **GBY** » Sat Jun 12, 2004 2:37 pm

Per wrote:
GBY wrote:Finding the number of the largest clique is indeed one way to solve the problem.In this problem you needn't find the largest clique of the whole graph but the one which contains current piece(that's enough).So using loops to count is enough.
I don't understand this. By "number" of the largest clique, do you mean something else than size? In the first test case I posted, the largest clique has size 2, yet the output should be 3.

I mean finding how many independent largest cliques there are by saying "the number".
For example in your (Per's) first case one of the independent largest cliques are AC BD E
So the answer is 3.

dll · Post by **dll** » Sun Jun 13, 2004 12:10 pm

I output the same as Per's output, but still get WA, anyone post some test cases for me ?
thanks.

howardcheng · Post by **howardcheng** » Thu Jun 17, 2004 6:15 pm

How does one do graph coloring quickly enough for this problem?

shuniu · Post by **shuniu** » Thu Jun 17, 2004 6:36 pm

I used backtracking for this problem.

First assume one color is enough,
then proceed to color each vertex with the color,
each time checking whether the coloring is valid.

If one color does not suffice, assume two colors.
color the first vertex with color 0.
color the second vertex with color 0,
if valid, try to color the third vertex...
color the second vertex with color 1,
if valid, try to color the third vertex...

If two colors not enough, try three colors...

You can limit the bracktracking by assuming color 0 is always first and color N never appears until color (N-1) is already used.

I guess you can also separate the graph into connected components, and then try to color each component separately.

shuniu · Post by **shuniu** » Fri Jun 18, 2004 5:04 pm

Here are some random generated test cases.

Input:

Code: Select all

20
18 143
N I
Q G
N B
J I
H C
B I
R Q
Q O
L I
Q M
D I
A H
Q H
K J
Q E
C N
A E
B L
J R
K O
L C
D Q
O E
K F
G R
L O
G P
I C
D M
J H
G M
J C
N Q
C R
H R
M F
Q P
O P
K Q
J B
I H
F I
L K
F B
F J
L H
O C
D L
E I
N O
F Q
G N
D P
N K
D F
O R
A P
P I
A R
G I
K R
J O
A M
G H
B P
B Q
P R
A Q
R E
D A
B E
M K
F O
M L
M H
J G
M N
K E
F N
P L
D R
D H
C G
A K
O A
F P
C Q
M C
O B
M B
J L
G L
B C
P E
Q J
Q I
P C
R N
J A
H N
K I
L N
C F
M O
P N
D O
R B
H E
G E
R M
F H
B G
P H
E L
C D
O I
E M
A L
J M
B K
O H
I M
E N
A N
M P
C K
L F
A B
F E
R F
G O
I R
D N
E J
D G
G A
N J
B D
P K
L R
K G
L Q
C E
3 1
A B
15 61
O A
G L
L I
M K
F E
N O
I K
I O
J N
H D
A I
J C
J E
L A
E O
G O
L E
L K
K F
G M
B L
O M
E D
J M
N L
J L
D O
B G
M I
D G
E B
I H
C N
G K
G I
F D
I C
J H
C H
B N
J I
D K
H O
M A
K H
L D
N G
B K
F L
L H
N M
H B
D M
G A
K N
A J
L C
C M
C B
B D
K A
3 2
A C
A B
16 112
P C
N J
B F
L J
D B
A K
G F
E H
O M
J P
E C
F C
D N
N H
J E
D I
J B
A H
E O
G L
K N
H G
P N
M G
O H
O I
N C
G B
D A
D E
N M
M D
B I
N F
G A
L B
D H
K B
A I
B O
K P
P B
J D
K F
A P
K I
P E
L H
I F
L K
C A
G P
D L
H J
M C
F L
G N
I H
C K
P D
D O
A L
K D
H M
J C
I G
J F
C I
L P
E N
P H
P I
O N
O L
F O
L C
M L
O G
G E
M B
H C
C G
K H
O P
O J
M A
E A
I J
E I
E K
D C
C B
A N
I L
F A
D F
D G
N L
M P
M E
I M
M K
K G
E B
E L
A B
N I
B N
A O
A J
M F
K J
15 44
M E
D G
I F
K O
K A
B L
F K
G F
C H
E F
I J
H B
A E
M D
E C
G L
F A
G A
O E
L M
M C
M A
K D
G K
I G
G O
O H
O F
D J
A B
B K
M H
F N
M N
K H
C J
D N
H A
I L
N L
E H
C L
I B
H G
12 21
H F
D E
J B
E B
F A
G H
C K
K B
C J
J F
A D
I G
L J
D L
I L
H L
L C
F B
C D
D B
G L
8 4
A E
F H
C E
C D
2 0
17 131
I M
H M
O L
P I
M K
E B
J I
G C
F O
G M
A O
F E
K Q
H O
J N
E G
E A
M A
H F
N A
D K
L Q
H P
F K
J L
J P
N P
F L
M N
F C
E H
L A
J A
B K
M L
P O
G P
F A
A H
J O
P Q
O I
D G
Q E
O M
F B
G K
N B
H Q
Q A
M E
N Q
B L
G Q
E O
F N
H J
Q J
D O
M P
K L
Q I
Q F
D J
O Q
B A
K A
F G
I C
D Q
O G
D N
D F
M B
J M
P D
I E
N L
D B
G N
A C
C L
I B
C N
G A
N E
B O
M F
J B
P K
A D
J K
H G
N K
H D
Q M
C E
H K
H I
J E
I F
K C
H N
I A
L G
I K
N O
O K
D I
L E
P C
C D
P B
G J
F P
M C
N I
C J
H C
L H
B C
H B
O C
Q C
B G
P E
I L
L P
D E
F J
L D
13 9
J M
J C
J A
L A
L M
B L
D B
D G
L G
11 40
A C
D C
J F
C K
B H
B F
B G
G E
F A
D H
D J
F C
A G
J A
G K
C B
D K
G D
G I
J K
H G
K H
J B
J H
H F
D F
F G
A B
I A
D E
I C
F E
F I
I K
C H
A H
J E
J G
E C
B E
6 10
B A
D C
A D
F B
B E
D F
E D
C F
A F
B C
1 0
6 10
A C
C B
E C
E F
F D
A F
A D
F C
C D
A E
5 8
E A
A D
B D
B A
C B
D E
B E
C D
18 21
A H
N R
H Q
J L
F B
P E
K E
M Q
G J
H G
M D
N A
F H
O K
N D
M A
B J
B K
Q N
G F
K A
13 21
I D
F E
H E
F B
K L
I M
K B
K M
E B
C G
I K
C A
J I
L G
A I
L D
C H
D B
J E
B M
A L
14 90
M L
F N
N E
K L
G H
N G
I K
I J
M K
L D
K F
D J
A G
L I
B J
B K
H C
B G
C K
I C
E J
A I
H D
H L
B L
M G
A J
E L
G J
F J
H N
J M
D A
C B
K G
M E
M C
B D
I E
F H
D E
H K
L F
H I
G D
A C
B E
C L
J H
L N
F B
H B
I B
I M
H M
D I
N B
L A
F D
J C
H A
M F
N C
E H
E A
G F
F C
B A
D M
I N
C G
L G
K A
N J
N K
J K
C D
K E
N A
D K
E C
F E
I F
M A
L J
G E
I G
B M
N D
A F
9 21
F G
E B
I E
F D
A G
A I
A B
C H
H E
B C
D I
H B
F B
B I
C G
E G
F H
B D
C F
G B
G D

Output:

Code: Select all

howardcheng · Post by **howardcheng** » Sat Jun 19, 2004 2:41 am

Thanks, I got AC now. I looked for the largest clique first and start searching from there.