b*********n
发帖数: 1258 | 1 Suppose there are n cities, and there may / may not be flight route
between c1 to c2. Design data structure to store this information and write
a function that receives two cities name, and return whether or not there is
a flight between them (either directly or through connections) | k*k
发帖数: 49 | 2 DP + Adjacent Matrix
for k = 1 to N //intermediate nodes
.....for a = 1 to N{
.........for b = 1 to N{
.............if (tlb[a][k] == 1 && tlb[k][b]==1){
................tlb[a][b] = 1;
..........}
.....}
}
bool isConnect(city a , city b)
..... return tlb[a][b];
construction time: O (N^3)
query time: O (1) | k***e
发帖数: 556 | 3 transitive closure problem
can use all sources shortest path algorithm to solve it
write
is
【在 b*********n 的大作中提到】
: Suppose there are n cities, and there may / may not be flight route
: between c1 to c2. Design data structure to store this information and write
: a function that receives two cities name, and return whether or not there is
: a flight between them (either directly or through connections)
| H*****L
发帖数: 5705 | 4 any thought?
construct the trie such that all flights sharing >=1 common city belong to
one branch
input:AB,BC,DE
output: root - A-B-C
- B-C
- D-E
given city x,y, return substring(x,y)|substring(y,x)
write
is
【在 b*********n 的大作中提到】
: Suppose there are n cities, and there may / may not be flight route
: between c1 to c2. Design data structure to store this information and write
: a function that receives two cities name, and return whether or not there is
: a flight between them (either directly or through connections)
| g*******y
发帖数: 1930 | 5 我觉得这个图问题，就是找连通components，可以用disjoint-set数据结构 |
|
