1. Suppose you are given the adjacency matrix representation M of a directed graph G = (V,E). Note that the size of M is Θ(n2). The goal here is to determine if there is a node of G with in-degree n−1 and out-degree 0 (that is, all other nodes point to it and it points to no other node). Give an algorithm to do this which runs in Θ(n) time (so not Θ(n2)). [5 points2. Suppose you work for a lab which is studying butterflies. It has a sample of n butterflies, L1,L2,…,Ln. The researchers have made a series of r determinations determining whether two butterflies belong to different species. A determination is of the form (i,j), and it means that Li and Lj belong to different species. Your job is to give an O(n+r) time algorithm to decide whether the determinations are consistent with the butterflies belonging to just two species. (Note: it is possible that they could belong to three or more species, but that is a separate question.) [5 points]