GraphStronglyConnectedComponent.m

/*
a strongly connected component of a directed graph G = (V, E) is a maximal set of vertices C ⊆ V 
such that for every pair of vertices u and v in C, we have both u ~~> v and v ~~> u; 
that is, vertices u and v are reachable from each other.
*/

/// Call the below method to find out the strongly connected component
+ (void)stronglyConnectedComponent:(NSArray<NSArray<NSNumber *> *> *)mat {
    
    NSMutableArray<NSNumber *> *visited = @[].mutableCopy;
    NSMutableArray<CCMutableNumber *> *finishTime = @[].mutableCopy;
    
    for(NSUInteger i = 0; i < mat.count; ++i){
        visited[i] = @(NO);
        finishTime[i] = [[CCMutableNumber alloc] initWithNumber:@(NSNotFound)];
    }

    [[self class] computeFinishTimeForAdjacencyMatrix:mat visited:visited finishTime:finishTime];
    NSMutableArray<NSMutableArray<NSNumber *> *> *mut = [[self class] transposeOfAnArray: mat];
    [[self class] printDFSInDescendingOrderOf:finishTime matrix:mut];
}

+ (void)printDFSInDescendingOrderOf:(NSMutableArray<CCMutableNumber *> *)finishTime matrix:(NSArray<NSArray<NSNumber *> *> *)mat {
    
    [finishTime sortUsingComparator:^NSComparisonResult(CCMutableNumber *  _Nonnull obj1, CCMutableNumber *  _Nonnull obj2) {
       
        return [obj1.num compare:obj2.num];
    }];
    
    NSMutableArray<NSNumber *> *visited = @[].mutableCopy;
    for(NSUInteger i = 0; i < mat.count; ++i){
        visited[i] = @(NO);
    }
    NSUInteger count = 0;
    for(NSUInteger i = 0; i < finishTime.count; ++i) {
        if(!visited[i].boolValue) {
            Log(@"Strongly Connected component No %lu", count);

            [[self class] DFSWithAdjacencyMatrix:mat root:i visited:visited];
            count += 1;
        }
    }
    
}
+ (void)DFSWithAdjacencyMatrix:(NSArray<NSArray<NSNumber *> *> *)mat root:(NSUInteger)idx visited: (NSMutableArray<NSNumber *> *)visited {
    
    visited[idx] = @(YES);
    Log(@"%lu", idx);
    
    for(NSUInteger i = 0; i < mat[idx].count; ++i) {
        if([mat[idx][i] isEqualToNumber:@(YES)] && !visited[i].boolValue) {
            [[self class] DFSWithAdjacencyMatrix:mat root:i visited:visited];
        }
    }

}

+ (NSUInteger)maximumInArray:(NSArray<NSNumber *> *)arr {
    NSUInteger max = NSIntegerMin;
    NSUInteger idx = NSNotFound;
    
    for(NSUInteger i = 0; i < arr.count; ++i) {
        if(max < arr[i].integerValue) {
            max = arr[i].integerValue;
            idx = i;
        }
    }
    
    return idx;
}

+ (void)computeFinishTimeForAdjacencyMatrix:(NSArray<NSArray<NSNumber *> *> *)mat visited:(NSMutableArray<NSNumber *> *)visited finishTime:(NSMutableArray<CCMutableNumber *> *)finishTime {
    
    CCMutableNumber *time = [[CCMutableNumber alloc] initWithNumber:@(1)];
    for(NSUInteger i = 0; i < mat.count; ++i) {
        if(!visited[i].boolValue) {
            [[self class] computeFinishTimeForAdjacencyMatrix:mat visited:visited finishTime:finishTime root:i time: time];
        }
    }
}

+ (void)computeFinishTimeForAdjacencyMatrix:(NSArray<NSArray<NSNumber *> *> *)mat visited:(NSMutableArray<NSNumber *> *)visited finishTime:(NSMutableArray<CCMutableNumber *> *)finishTime root:(NSUInteger)idx time:(CCMutableNumber *)time {
    
    visited[idx] = @(YES);
    Log(@"%lu", idx);
    
    for(NSUInteger i = 0; i < mat.count; ++i) {
        if([mat[idx][i] isEqualToNumber:@(YES)] && !visited[i].boolValue){
            time.num = @(time.num.integerValue + 1);
            [[self class] computeFinishTimeForAdjacencyMatrix:mat visited:visited finishTime:finishTime root:i time:time];
        }
    }
    
    time.num = @(time.num.integerValue + 1);
    finishTime[idx] = time.copy;
}

+ (NSMutableArray<NSMutableArray<NSNumber *> *> *)transposeOfAnArray:(NSArray<NSArray<NSNumber *> *> *)arr {
    NSMutableArray<NSMutableArray<NSNumber *> *> *mut = @[].mutableCopy;
    
    for(NSUInteger i = 0; i < arr.count; ++i) {
        mut[i] = arr[i].mutableCopy;
    }
    
    for(NSUInteger i = 0; i < arr.count; ++i) {
        for(NSUInteger j = 0; j < arr[i].count; ++j) {
            mut[j][i] = arr[i][j];
        }
    }
    
    return mut;
}