10972 - RevolC FaeLoN

[Wei-Ming Chen]

Why the output are 1 & 2 ?
I thought they were 0 & 1 ....

[Adrian Kuegel]

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).

[artem]

Who may check this input

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

my output is

Code: Select all

0
2
1
3
3
0
0
3
0
2
2
0
19
999
2

Is it right?

[Moha]

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

[polone]

I don't know how to solve ths problem.
Just found a stubid greedy method
could someone who got ac explain it?

[Cho]

It's about biconnected component. Revising textbook may help.
CLR Ch.23, p.495, problem 23-2.

[Moha]

Yes, I use same algorithm. I tried to find cut-edge in graph.

[Monsoon]

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)?

[sclo]

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 can prove the general case now. I think there are 2 cases.
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.

[Monsoon]

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...

Code: Select all

cut after acc, finally found a stupid bug :-)

[red_apricot]

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.