图论：查找购买某物品的顾客购买最多的其他物品

题目大意：有一个数组存储了多个顾客的购物清单。指定一个物品item1,求出购买了item1的顾客除了购买item1外，购买最多的物品。

很实用的小题目。电商网站市场能看到。


来源
http://blog.chinaunix.net/uid-26750075-id-3370694.html 

分析：
简单的图论题目。首先把数组转成图的邻接表表示。实际就是求出到指定顶点item1距离为2的所有顶点中，具有路径最多的那个。

考虑到C还得自己实现hash,就用perl写了下。 perl真是舒畅，可惜很多排序的古怪用法都往了，不然能短很多。

Question:
We have an array representing customer’s shopping records.
For example, it’s an array like this:
custA, item1,
custB, item1,
custA, item2,
 custB, item3,
 custC, item1,
 custC, item3,
 custD, item2,
This array indicates that customer A bought item 1, customer B bought item 1, customer A bought item 2, customer B bought
item 3, etc..
For a given item X and shopping records array, write code to find out what else (item Y) was bought mostly by the customers
who bought item X.
For example, in above example, if X is item 1 then Y should be item 3.
Rules:
1.  One customer can only buy one item once.
2.  The mostly brought item should not be item X.
3.  If no customer brought item X, then return “None”
4.  If all the customers who brought item X only brought item X, then return “None”
5.  The first line of input is the item X. The second line of input is the shopping record array, this shopping record array is
split by space.
6.  If there are many other mostly brought items which have equally brought times, then return any one of those items.
Examples:
Input1:
item1
custA item1 custB item1 custA item2 custB item3 custC item1 custC item3 custD item2
Output1:
item3
 
Input2:
item2
custA item1 custB item1 custC item1 custA item2 custB item3 custA item3
Output2:
item1   

my @input = ("A","item1","A","item2","B","item1","B","item2","C","item2","C","item3");

sub createGrap{
    my %hash;
    my @all = (@_, reverse(@_));
    for(my $i = 0; $i<@all; $i+=2){
    if(!exists($hash{$all[$i]})){
            my @tmp = ();
            $hash{$all[$i]} = @tmp;
        }
    my @tmp = @{$hash{$all[$i]}};
    push(@tmp, $all[$i+1])
    $hash{$all[$i]} = @tmp;
    }

    return %hash;
}

sub getMax{

    my ($item, %hash) = @_;
    return "NO item $item found." if(!exists($hash{$item}));

    my @customers = @{$hash{$item}};
    my %counter;
    for(@customers){
        for( @{$hash{$_}}){
            $counter{$_} = 0 if(!exists($counter{$_}));
            $counter{$_}++;
        }
    }
    my $max;
    for( keys(%counter)){
                if($_ ne $item){
         $max = $_ if(!defined($max) || $counter{$max}<$counter{$_});
                }

    }
    return $max;
}

my %grap = createGrap(@input);

print( getMax("item2", %grap));