| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
This problem on UVA was categorized under bipartite matching. I am not able to figure any algorithm for this. If we make a graph, where edge denotes that 2 people can form a couple, wouldn't the problem be of maximum independent set ?? It would be really great if someone can give some hint about this.
Thanks
Independent set is not NP problem for biparite graph. You can prove that answer always is V — |maximal matching|. I'm not ready to prove this fact now.
As a proof: In general graphs Independent set = V — minimal vertex cover. You can prove that minimal vertex cover is maximal matching in bipartite graphs. It's called [Konig's theorem](http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory)) and it's a proof there, too.
minimal vertex cover is maximal matching in bipartite graphs
How about isolated vertexes? They increse the minimal vertex cover, but don't change the maximal matching.
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=392&page=show_problem&problem=3642
Heyy, can you tell how is this a bipartite graph ?
That's problem 'cover graph with minimal number of paths', doesn't it?
UPD: acyclic graph
Nothing
http://www.spoj.com/problems/ANGELS/
Can you please explain how do we construct a bipartite graph in this ? Thanks