Hi,
I'm starting to solve problems in codeforces with Haskell. But I have had obstacles with the way to represent a graph. How can I do it efficiently?
Thanks :]
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi,
I'm starting to solve problems in codeforces with Haskell. But I have had obstacles with the way to represent a graph. How can I do it efficiently?
Thanks :]
Name |
---|
You can basically do the same thing you would do in C++ or Java, so if you have a simple directed graph, an adjacency list representation could be
adjList :: Array Int [Int]
, so for every vertexv
,adjList ! v
is the list of its adjacent vertices.In fact, this type of graph representation is provided in the module
Data.Graph
(link), which is part of thecontainers
package and can be used on Codeforces. That module even provides implementations of some graph algorithms out of the box, including topological sorting and finding BCCs.In general though, Haskell is probably not the best suited language for graph algorithms, because many of them rely heavily on mutable data structures and are rather imperative in nature, which doesn't really fit Haskell's purely functional style.
So if your graph problem happens to be solvable using just
Data.Graph
you can use that, otherwise you might be better off using a different language instead. (That being said, you certainly can do it in Haskell, but for this you might want to read up on mutable arrays in Haskell).Thanks :)