OJ Board

Posted: **Wed Dec 12, 2001 8:39 pm**

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!

Posted: **Fri Jan 11, 2002 7:10 pm**

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

Posted: **Sat Jan 12, 2002 1:05 am**

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.

Posted: **Fri Apr 05, 2002 4:49 pm**

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

Posted: **Fri Apr 05, 2002 6:06 pm**

hello~ the output of my accepted program is 6.

Posted: **Wed Aug 25, 2004 4:21 pm**

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.

Posted: **Thu Aug 26, 2004 10:36 am**

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.

Posted: **Sat Apr 30, 2005 3:46 pm**

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

Posted: **Tue Sep 06, 2005 4:53 pm**

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

Is that right? Thanks.

Posted: **Wed Sep 07, 2005 5:56 am**

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

Posted: **Fri Dec 16, 2005 8:42 am**

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

Posted: **Mon Oct 06, 2008 5:25 am**

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.

Posted: **Sat Apr 28, 2012 7:55 am**

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

OJ Board

10178 - Count the Faces.

10178 - Count the Faces.

10178: Count the Faces

10178 Count the faces WA???

10178

Re: 10178 Count the faces WA???

Re: 10178 - Count the Faces

10178 - Count the Faces