Вы уверены что О(n) ? О_о

vb.net, Console Application
Module Module1
Sub Main()
'--- Create matrix
Console.Write("Count of men=")
Dim N As Int16 = CInt(Console.ReadLine) - 1
Dim M(N, N) As Int16
'--- Fill matrix
For I As Int16 = 0 To N
Console.WriteLine("Man-{0} knows :", I)
For j As Int16 = 0 To N
If j = I Then Continue For
Dim YN As Char
Do
Console.Write(" Man-{0} (Y/N)>", j)
YN = Console.ReadKey.KeyChar
Console.WriteLine()
Loop Until YN Like "[YyNn]"
If YN Like "[Yy]" Then
M(I, j) = 1
ElseIf YN Like "[Nn]" Then
M(I, j) = 0
End If
Next
Next
'--- Operation: Paparacci
Dim O, F As Int16
Dim NoBody As Boolean = True
For I As Int16 = 0 To N 'for each man
F = 0
For J As Int16 = 0 To N
F += M(I, J) 'sum, how much he knows
Next
If F = 0 Then 'knows nobody - half-famous
O = 0
For J As Int16 = 0 To N
O += M(J, I) 'sum, how many knows him
Next
If O = N Then 'all knows - full-famous
Console.WriteLine("Man-{0} is famous!", I)
NoBody = False
End If
End If
Next
If NoBody Then Console.WriteLine("No one is famous...")
'---------------------------------
Console.WriteLine("Enter to exit")
Console.ReadLine()
End Sub
End Module

забыл спросить только, что такое "O(n)"?

Не очень!!!

Задача нахождения столбца i заполненного единицами (кроме элемента в диагонале а(i,i)), но в соответствующем i-строке должны находится одни нули. Причем, операции сравнения, присваивания, сложения, и т. п. не должны превышать числу С*N, где С – некоторая константа меньше N.

вы говно

моцк безнадежно умер ещё на чтении условия.
ушел хоронить.

Допустим для простоты что на главной диагонали все 1 (любой человек знает о себе) Алгоритм работает так: начинаем с клетки 1:1 и идём вниз до первого 0. Допустим мы нашли первый 0 в строке i - теперь идем на клетку i+1:i+1 и снова начинаем двигаться вниз до первого 0 - скажем в строке j>i - теперь идем на j+1:j+1 и так далее... Допустим мы добрались таким образом до последней строчки матрицы спускаясь по столбику K - либо K - знаменитость - либо знаменитостей нет. Проверка на знаменитость берет 2N плюс итерации описанные выше берут не больше чем N - Таким образом весь алгоритм <= 3N

Алгоритм, который предложил AlexeyK, почти верен. После нахождения 0 в строке с номером i необходимо переходить в клетку с номером (i,i), т.к. "отсекать" i-ю вершину рано!
Небольшие пояснения:
Будем называть текущий столбец "просматриваемым". Пусть просматриваемый столбец имеет номер i, тогда "отсекаем" все вершины, которые в просматриваемом столбце содержат 1 (по критерию "знают хотя бы одного"), в случае если находим 0 в j-й строке (j>i), отсекаем i-ю вершину (по критерию "о нем не все знают").
В итоге окажемся в k-м столбце в последней строке. k-я строка последней содержала 0. Согласно написанному выше, все вершины 1..k-1 были отсеяны ранее. Все вершины k+1..N, если k<N (где N - число вершин графа) отсеиваются (по критерию "знают хотя бы одного"). Т.о. единственный кандидат в знаменитости - k-я вершина графа.