10972 - RevolC FaeLoN
Moderator: Board moderators
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
10972 - RevolC FaeLoN
Why the output are 1 & 2 ?
I thought they were 0 & 1 ....
I thought they were 0 & 1 ....
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
For first input, you need to add an edge between 1 and 3
(the edge orientations can then be 1-> 2, 2->3, 3-> 1 or 1->3, 3->2, 2->1)
For second input, one solution would be to add an edge between 10 and 7 and between 10 and 6 (you cannot use less edges, since 10 has no connection at all before, so it needs an ingoing and an outgoing edge).
(the edge orientations can then be 1-> 2, 2->3, 3-> 1 or 1->3, 3->2, 2->1)
For second input, one solution would be to add an edge between 10 and 7 and between 10 and 6 (you cannot use less edges, since 10 has no connection at all before, so it needs an ingoing and an outgoing edge).
Who may check this input
my output is
Is it right?
Code: Select all
3 3
1 2
2 3
3 1
10 11
1 2
2 3
3 1
3 7
4 5
5 6
6 4
7 9
6 3
9 8
7 8
3 2
1 2
2 3
3 0
6 4
1 2
1 3
1 4
5 6
1 0
0 0
7 6
1 2
1 3
2 4
2 5
3 6
3 7
20 20
1 3
3 5
5 7
7 9
9 11
11 13
13 15
15 17
17 19
19 20
20 2
2 4
4 6
6 8
8 10
10 12
12 14
14 16
16 18
18 1
10 12
1 2
2 3
3 4
4 2
1 5
5 6
6 7
7 5
1 8
8 9
9 10
10 8
10 8
1 3
3 5
5 7
7 9
2 4
4 6
6 8
8 10
5 6
1 2
1 3
2 4
3 5
4 1
5 1
20 1
7 11
1000 1
1000 999
14 16
1 2
2 3
2 4
3 4
4 5
4 6
5 6
6 7
7 8
7 9
8 9
10 11
10 12
11 14
12 13
13 14
Code: Select all
0
2
1
3
3
0
0
3
0
2
2
0
19
999
2
My accpeted solution gives me these anserws:
Code: Select all
0
2
1
3
3
0
0
2
0
2
2
0
19
999
2
Cut-Edge
Yes, I use same algorithm. I tried to find cut-edge in graph.
tests
Could anyone post some tricky tests cases? Thanks in advance ![:wink:](./images/smilies/icon_wink.gif)
[Edit]
I have one (probably silly) question, suppose we have a graph G, we create a graph G', where nodes are connected componets from G, and egdes are bridges from G. G' is a forrest. Now i think that answer i seek is ceil(number_of_leaves_in_G' / 2). Where single node i count as 2 leaves. I can't find counter example to this, but i can't also prove it. Could anyone show me counter example (using this idea i got wa so i consider it to be wrong)?
![:wink:](./images/smilies/icon_wink.gif)
[Edit]
I have one (probably silly) question, suppose we have a graph G, we create a graph G', where nodes are connected componets from G, and egdes are bridges from G. G' is a forrest. Now i think that answer i seek is ceil(number_of_leaves_in_G' / 2). Where single node i count as 2 leaves. I can't find counter example to this, but i can't also prove it. Could anyone show me counter example (using this idea i got wa so i consider it to be wrong)?
Re: tests
I can prove the general case now. I think there are 2 cases.Monsoon wrote:Could anyone post some tricky tests cases? Thanks in advance
[Edit]
I have one (probably silly) question, suppose we have a graph G, we create a graph G', where nodes are connected componets from G, and egdes are bridges from G. G' is a forrest. Now i think that answer i seek is ceil(number_of_leaves_in_G' / 2). Where single node i count as 2 leaves. I can't find counter example to this, but i can't also prove it. Could anyone show me counter example (using this idea i got wa so i consider it to be wrong)?
I'll only look at the interesting case, we have more than 1 node (biconnected components).
Let n be the number of leaves, k be the number of single nodes.
Proof:
1) we need at least ceil(n/2)+k = ceil((n+2k)/2) additional edges.
Suppose we added less than ceil(n/2)+k additional edges, then there will exist some nodes of deg 1 (leaves) or deg 0 (single nodes) even after we added edges. For the case of deg1, then clearly we can either enter or leave the node, but not both, so it is not strongly connected to other nodes. For the case of deg 0, it is not connected, so it can't be strongly connected to other nodes.
2) we need at most ceil(n/2)+k additional edges.
We use k-1 edges to connect the k single nodes together, we use ceil(n/2) edges to connect the leaves together into a single component,
Now, if there is at least 2 leaves, remove one of the edges connecting 2 leaves, and use it to connect a single node and one of the leave, and add another edge to connect the remaining leaf with the remaining node. We used a total of ceil(n/2)+k edges.
If there are only k single nodes, clearly k edges are sufficient to form a cycle.
Now we must prove that we can give an orientation of the undirected edges to solve the problem by adding the same number of edges as above.
It is left as an exercise. It is a not so straight forward induction proof. One approach to show that we can swap the edges that we have added until we have a single biconnected component, and then show that any biconnected graph can be given an orientation to become a strongly connected digraph.
Last edited by sclo on Fri Sep 01, 2006 9:32 am, edited 1 time in total.
Thanks sclo, i will think how to proof the last part
Thank you very much for the idea of proof.
But if my aproach is correct so maybe somebody would tell me where i have mistake...
![:D](./images/smilies/icon_biggrin.gif)
But if my aproach is correct so maybe somebody would tell me where i have mistake...
Code: Select all
cut after acc, finally found a stupid bug :-)
-
- New poster
- Posts: 48
- Joined: Sun Jun 22, 2014 6:14 am
Re: 10972 - RevolC FaeLoN
Certainly an amazing problem: so simply formulated yet conceptually rich. Now I've got a questions: are there duplicate edges? i.e. can (x,y) be listed twice? I know in that case we would simply merge x and y and consider them as one vertex, but that would only lengthen the code.
--Thanks!
EDIT: Checked with assert, and there seems to be no multiple edges.
--Thanks!
EDIT: Checked with assert, and there seems to be no multiple edges.