## 10178 - Count the Faces.

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 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!
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.
Last edited by Adrian Kuegel on Tue Jan 07, 2003 8:35 pm, edited 2 times in total.
Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
hello~ the output of my accepted program is 6.
Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Contact:

### 10178: Count the Faces

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.
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
New poster
Posts: 1
Joined: Wed Apr 23, 2003 1:26 am
Location: Barcelona

### 10178 Count the faces WA???

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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### 10178

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.
I stay home. Don't call me out.
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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``````
I stay home. Don't call me out.
Pregunt
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:

### Re: 10178 Count the faces WA???

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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10178 - Count the Faces

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
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

### 10178 - Count the Faces

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.