Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
//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
You can’t perform that action at this time.