10178 - Count the Faces.

[..]

I know that the graph have many components. But I still got WA many times, can anyone give me some tricky input for testing?
Thanks a lot!

[Adrian Kuegel]

I have a few questions:
Is the edge between a and A an edge to the vertex itself or not?
What is the answer to this input (or is it not a valid one?):
9 9
A B
B Z
Z A
C E
E F
G E
A A
B A
E C

The answer of my program is 2

[Adrian Kuegel]

Finally I got Accepted. The sample input I have posted is valid, but my output was wrong, because if there are more than one edges between two vertices, they have all to be counted. Therefore the output is 5.

[Kamp]

I have some troubles with that problem...
What will be the answer of this input:

5 9
A B
B C
C A
A A
B D
C E
D E
B D
C E

[LittleJohn]

hello~ the output of my accepted program is 6.

[Guest]

Hello,
I need some clarification on this problem. I thought this problem needs the formula r=e-v+2 where r=no of regions, e=no of edges & v=no of vertices. So given v & e, r could be easily calculated. I also thought that the other information given are not required. But I've got WA and cannot figure out what's wrong. Is this a big integer problem? What else is there that I've missed?
I would really appreciate any reply.
Thanks in advance.

[sohel]

I haven't got it AC but I think the formula that you have given works for only connected graphs.
...And the graph may not be connected.

[atomicalnet]

Hi,

I can't get this problem AC. My algortihm analyses the given graph, it tries to see how many non-connected graphs are, then counts all the regions for every non-connected graph (using Euler's formula r=2-n+e), as a result i've got the sum of all the regions of all the disconnected graphs. I assume that two or more edges can be connected to the same nodes, thus generating antoher face.

Because every time I count a graph I'm counting the outside region (the 6th face in the given example), I discount n-1 to the result, being n the number of total disconnected graphs.

I've tried many extreme cases and it seems to work fine, but I must be missing something. I would apreciate it if someone could give me a point in the right direction.

Regards

[ImLazy]

This is my input:

Code: Select all

41 266
a d
a f
k a
n a
a s
v a
a w
A a
a B
a C
F a
a J
O a
b c
b d
i b
b r
b t
b v
b A
b G
I b
L b
M b
c d
c e
c m
c p
q c
t c
v c
c y
c B
E c
H c
c J
c M
d f
d t
d w
d y
d F
G d
I d
K d
M d
d O
g e
k e
e m
s e
e x
z e
e I
K e
e M
e O
f j
k f
f l
f m
f n
f o
f p
f q
f t
v f
f y
z f
A f
C f
E f
J f
f L
M f
f O
g i
g p
s g
B g
g E
F g
J g
l h
h o
h q
h x
h y
z h
A h
E h
h H
h I
N h
h O
i o
r i
i u
z i
C i
i F
J i
m j
j o
j t
j u
j v
z j
j D
j E
H j
J j
m k
k n
y k
k A
E k
G k
k I
K k
N k
k O
l n
o l
l p
l y
l G
l I
J l
K l
M l
N l
m n
o m
s m
u m
m w
A m
m D
m G
M m
n u
v n
w n
A n
H n
n J
L n
O n
o p
o s
o u
y o
o F
G o
o H
I o
J o
o K
L o
N o
t p
w p
p x
z p
A p
C p
F p
p H
N p
p O
r q
v q
q x
A q
D q
F q
q G
q I
L q
q O
t r
u r
r z
r C
r D
r F
r M
r N
O r
t s
x s
y s
s z
u t
t w
C t
t F
J t
t K
t M
t O
z u
u H
u L
u M
z v
v B
v I
v L
M v
v N
w x
w K
x B
E x
x F
x H
x N
y A
y C
E y
G y
I y
K y
L y
A z
B z
z J
z K
z L
N z
A B
A H
A I
A K
L A
A O
B E
F B
M B
D C
I C
D E
D F
D H
I D
F E
G E
H E
I E
J E
E L
N E
F K
G I
K G
H M
I M
J L
M J
J O
L N
O L
M N
O M

40 205
h a
n a
a p
r a
a u
a w
a x
a J
e b
f b
b h
b i
b l
b q
b u
b x
b y
F b
b K
b M
d c
g c
c p
v c
x c
A c
c C
c E
G c
H c
c M
N c
n d
o d
p d
s d
d A
d F
G d
d K
i e
l e
e m
e p
e q
e r
s e
e v
x e
A e
C e
K e
e M
f j
l f
n f
f o
s f
f t
f F
G f
H f
K f
f L
M f
f N
g i
n g
o g
q g
r g
A g
G g
g L
j h
h l
p h
r h
h u
x h
h A
F h
H h
K h
L h
n i
i t
i F
i L
m j
r j
j w
B j
E j
F j
j H
M j
k n
k v
k B
H k
J k
k M
s l
l u
l A
E l
l H
l J
l L
N l
p m
q m
r m
m x
C m
m G
H m
n q
n r
n w
y n
n z
n C
n J
K n
o v
y o
z o
o E
L o
M o
o N
t p
p x
p F
q r
q x
q H
J q
q N
t r
r x
r z
r D
I r
r M
N r
s x
s D
s F
I s
s L
s M
A t
t I
t L
u x
I u
M u
v w
C v
v G
L v
w x
w C
w E
w G
w K
L w
w M
z x
A x
C x
x I
J x
L x
x M
z y
G y
I y
z D
z E
z G
I z
J z
K z
L A
M A
B F
B I
B J
B N
C J
C K
N C
E I
N E
H F
K F
M F
H I
J H
K L
K M

4 2
c a
b d

23 65
b a
a o
p a
b d
b e
b g
b h
j b
b o
t b
u b
v b
c h
i c
j c
n c
c o
t c
w c
d j
m d
d s
d t
d v
w d
f e
n e
q e
f g
i f
k f
s f
g k
g n
g p
j h
m h
o h
r h
i r
t i
k j
m j
n j
q j
m k
k u
n l
l s
m n
m p
u m
n o
n p
o p
o r
t o
p r
s p
u q
w q
r t
w s
t v
w u

33 150
j a
r a
a s
C a
E a
c b
q b
b y
A b
b D
E b
c h
c i
k c
c m
q c
c u
y c
B c
D c
c F
d k
t d
d u
x d
C d
f e
k e
e m
n e
e u
e w
F e
e G
f h
f k
m f
f r
f t
f w
k g
g l
g n
p g
x g
y g
g C
E g
h i
h m
o h
t h
y h
D h
E h
h G
i k
i l
p i
i t
v i
i x
i y
F i
k j
j m
o j
p j
j r
s j
v j
j y
C j
n k
k o
p k
u k
v k
z k
k B
C k
D k
l n
q l
u l
l v
l B
C l
l D
l G
o m
m s
y m
C m
m G
q n
r n
w n
n x
y n
n B
G n
o p
u o
B o
F o
o G
q p
w p
p y
p A
p E
F p
q w
x q
q y
r s
w r
r B
r D
y s
E s
s F
u t
w t
x t
t z
t F
u w
x u
u y
u A
v y
v z
A v
E w
x y
B x
z y
A y
y E
z F
A B
C A
A D
B D
F B
C E
C G
E F

4 2
a c
b c

6 6
e b
f b
c d
e c
c f
d e

8 2
f c
h g

36 204
e a
a g
j a
a k
a p
s a
t a
a w
D a
E a
G a
J a
g b
h b
i b
m b
b n
o b
q b
b s
u b
w b
b D
c f
c i
j c
c n
c u
c w
z c
c F
c G
e d
f d
h d
k d
d o
p d
d A
d C
D d
E d
H d
I d
d J
e f
e k
l e
m e
e n
e o
w e
x e
e F
e G
f k
l f
m f
n f
f p
f x
f A
B f
f C
F f
G f
f H
g i
j g
g k
g r
g w
g y
g C
g F
g I
j h
h n
o h
t h
h u
w h
h C
h E
h F
h G
l i
i n
r i
u i
i w
i y
G i
i I
q j
j r
j v
G j
j J
o k
k r
w k
x k
A k
G k
H k
k I
k J
q l
r l
l w
x l
l y
H l
l I
m n
o m
m p
m r
m s
u m
z m
E m
J m
n o
n p
B n
F n
G n
n H
n I
n J
o u
o v
o y
o A
C o
o I
q p
r p
x p
B p
p D
p G
q u
q F
q J
r s
t r
x r
r z
E r
r F
J r
v s
s A
s C
s I
z t
A t
t B
t E
u y
C u
u E
G u
H u
J u
A v
v D
v G
v H
w x
w H
y x
x B
F x
x J
A y
B y
y F
y G
D z
z E
z F
z G
I z
A E
A G
D B
D C
C G
H C
C J
D E
D F
H D
E F
J E
H F
F I
F J
I G
J H

38 203
a i
n a
r a
a v
y a
a A
a B
a C
a F
b e
b p
q b
t b
b u
b z
B b
b C
b F
b G
b H
e c
c l
y c
z c
A c
c B
C c
c F
H c
e d
d h
d l
d p
u d
d v
d y
d z
d F
d K
d L
g e
e j
e k
l e
e o
e s
e w
y e
z e
e B
i f
p f
f q
f w
E f
I f
g j
g k
l g
m g
q g
g r
g B
g J
L g
i h
l h
h m
o h
h q
h t
h x
h y
h L
o i
i q
u i
i z
B i
j l
p j
y j
D j
L j
k n
k o
k q
k w
D k
l p
l s
A l
E l
l H
J l
m n
m o
t m
m v
w m
m B
m J
K m
L m
n o
x n
I n
n J
n K
L n
q o
o v
x o
o A
D o
E o
o H
o K
p r
p s
y p
p C
p E
s q
v q
q x
z q
A q
q K
q L
s r
u r
D r
G r
I r
r L
s t
u s
w s
s z
A s
s C
s H
x t
A t
G t
I t
t J
t L
z u
u A
B u
D u
E u
u G
x v
B v
H v
v I
J v
v L
y w
z w
w C
D w
w F
H w
I w
E x
x G
x L
y C
y D
y E
K y
z A
z C
z H
L z
C A
D A
F A
G A
B D
B E
F B
H B
B I
L B
C G
C I
L C
E D
G D
D L
E F
E G
J E
F H
I G
J G
G K
K J

And my output is:

Code: Select all

242
180
1
44
126
1
3
1
180
179

Is that right? Thanks.

[ImLazy]

Oh! I forget it is case sensitive. How careless I am! Now I get AC.
The right output for the input data above should be:

Code: Select all

227
167
1
44
119
1
3
1
170
167

[Pregunt]

I only used r=1+e-n+k, (k=number connected components of the graph).
Maybe you forgot that it is case sensitive
Input
2 0
2 1
A a
3 1
A a
3 3
a c
c A
a c
2 2
a a
A A
Output
1
1
1
2
3

[stcheung]

Another thing worth mentioning is that I think the same edge may appear multiple times in the input. i found that out because I keep getting RE at first when I assume each vertex has at most V edges. Once I changed that to 10*V it works for me.

[BUET]

The original graph may have many components. Let there are k components. Let the total number of faces is F.
Initially F = 0
In input edges we can have-
x x
for each occurrence of such edges, just F++
Again we can have
(x y) or (y x)
If we get total p occurrences of (x y) or (y x) F = F+(p-1)

Without considering the above edges, we now have a normal graph. In this graph for each k component
we have to find the number of vertices(n) and edges(e) separately;
(n1,e1),(n2,e2).........(nk,ek)
f1 = 2-n1+e1
f2 = 2-n2+e2
.
.
.
fk = 2-nk+ek
F = F +(f1+f2+.....+fk) - (k-1)--------(i)
We have to subtract (k-1) in equation (i), because every fi (1<=i<=k) counts outer face, but there is only one outer face
To find each (ni,ei) I have used DFS
So final F is our final answer.

Md. Shadekur Rahman
BUET, Dhaka, Bangladesh