Created
November 9, 2015 14:09
-
-
Save nbarnold01/404bae8390fd098834d4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Enter your code here. Read input from STDIN. Print output to STDOUT// | |
// main.m | |
// Breadth First Search: Shortest Reach | |
// | |
// Created by Nathan Arnold on 11/1/15. | |
// Copyright © 2015 Nathan Arnold. All rights reserved. | |
// | |
#import <Foundation/Foundation.h> | |
static int EDGE_LENGTH = 6; | |
NSMutableDictionary *hasVisited; | |
NSMutableDictionary *distanceFromRoot; | |
/* | |
Breadth-First-Search(G, v): | |
2 | |
3 for each node n in G: | |
4 n.distance = INFINITY | |
5 n.parent = NIL | |
6 | |
7 create empty queue Q | |
8 | |
9 v.distance = 0 | |
10 Q.enqueue(v) | |
11 | |
12 while Q is not empty: | |
13 | |
14 u = Q.dequeue() | |
15 | |
16 for each node n that is adjacent to u: | |
17 if n.distance == INFINITY: | |
18 n.distance = u.distance + 1 | |
19 n.parent = u | |
20 Q.enqueue(n) | |
*/ | |
void breadthFirstSearch(NSDictionary *graph, NSNumber *start, int numberOfNodes){ | |
NSMutableArray *queue = [NSMutableArray arrayWithCapacity:numberOfNodes]; | |
[queue addObject:start]; | |
while ([queue count]){ | |
NSNumber *currentNode = [queue firstObject]; | |
[queue removeObjectAtIndex:0]; | |
NSSet *children = graph[currentNode]; | |
long length = [distanceFromRoot[currentNode] longValue]; | |
[children enumerateObjectsUsingBlock:^(id obj, BOOL * stop) { | |
NSNumber *cachedDistance = distanceFromRoot[obj]; | |
if (!cachedDistance) { | |
distanceFromRoot[obj] = [NSNumber numberWithLong:(length + 1)]; | |
[queue addObject:obj]; | |
} | |
}]; | |
} | |
} | |
void processTestCase() { | |
int nodes = 0; | |
int edges = 0; | |
int start = 0; | |
scanf("%d %d", &nodes, &edges); | |
//key is nodeID, value is set of nodeIDs connected to node | |
NSMutableDictionary *graph = [NSMutableDictionary dictionaryWithCapacity:nodes]; | |
//Build the graph | |
for (int i = 0; i < edges; i++){ | |
int node1 = 0; | |
int node2 = 0; | |
scanf("%d %d",&node1, &node2); | |
NSNumber *num1 =[NSNumber numberWithInt:node1]; | |
NSNumber *num2 =[NSNumber numberWithInt:node2]; | |
NSMutableSet *set1 = graph[num1]; | |
NSMutableSet *set2 = graph[num2]; | |
if (set1) { | |
[set1 addObject:num2]; | |
} else { | |
graph[num1] = [NSMutableSet setWithObjects:num2, nil]; | |
} | |
if (set2) { | |
[set2 addObject:num1]; | |
} else { | |
graph[num2] = [NSMutableSet setWithObjects:num1, nil]; | |
} | |
} | |
scanf("%d", &start); | |
hasVisited = [NSMutableDictionary dictionaryWithCapacity:nodes]; | |
distanceFromRoot = [NSMutableDictionary dictionaryWithCapacity:nodes]; | |
breadthFirstSearch(graph, [NSNumber numberWithInt:start], nodes); | |
for (int i = 1; i <= nodes; i++) { | |
if (start != i) { | |
NSNumber *node = [NSNumber numberWithInt:i]; | |
if (distanceFromRoot[node]){ | |
printf("%d ",[distanceFromRoot[node] intValue] * EDGE_LENGTH); | |
} else { | |
printf("-1 "); | |
} | |
} | |
} | |
printf("\n"); | |
} | |
int main(int argc, const char * argv[]) { | |
// @autoreleasepool { | |
// insert code here... | |
int numberOfTestCases = 0; | |
scanf("%d", &numberOfTestCases); | |
for (int i = 0; i < numberOfTestCases; i++){ | |
processTestCase(); | |
} | |
// } | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment