p*****2
发帖数: 21240 | 1 一个无向图， 有n个vertices
每个vertice 用一个color来表示， color用int来表示
现在对于某种color来说，会对应几个点，如果这些点的邻居的color是不同的颜色，则
认为这两种不同的color有relation
那么现在求有最多relation的color，如果两种color的reliation数目一样多，则应该
选择color的int值更小的那个 |
l*********8
发帖数: 4642 | 2 My two cents:
遍历所有边，把color-color relations 存在multimap里面。
最后扫描multimap找出relation最多的color.
【在 p*****2 的大作中提到】
: 一个无向图， 有n个vertices
: 每个vertice 用一个color来表示， color用int来表示
: 现在对于某种color来说，会对应几个点，如果这些点的邻居的color是不同的颜色，则
: 认为这两种不同的color有relation
: 那么现在求有最多relation的color，如果两种color的reliation数目一样多，则应该
: 选择color的int值更小的那个
|
p*****2
发帖数: 21240 | 3
这道题就是数据结构题。没什么算法。
【在 l*********8 的大作中提到】
: My two cents:
: 遍历所有边，把color-color relations 存在multimap里面。
: 最后扫描multimap找出relation最多的color.
|
w***o
发帖数: 109 | 4 HashMap> map = new HashMap
Integer>>();
int[] max = new int[n]; // n = total number of colors
for(Vertex v : G.V()) {
for(Vertex w: v.adj()) {
if(w.color != v.color) {
if(map.containsKey(w.color)) {
HashSet set = map.get(w.color);
if(!set.contains(v.color)) {
set.add(v.color);
max[w.color]++;
}
} else {
HashSet set = new HashSet();
set.add(v.color);
map.put(w.color, set);
max[w.color]++;
}
}
}
}
int maxColor = 0;
for(int i = 1; i < n; i++) {
if(max[i] > max[maxColor]) maxColor = i;
}
return maxColor; |
l*********8
发帖数: 4642 | 5 输入的图是怎么存储的？ 还要实现图的数据结构吗？
【在 p*****2 的大作中提到】
:
: 这道题就是数据结构题。没什么算法。
|
p*****2
发帖数: 21240 | 6
输入是
一个整数数组，每个代表一个node的颜色
然后是一系列的关系
1 2
2 3
3 4
每一行代表一条边。1 2就是node1 和 node2 有一条边
需要自己定义数据结构
【在 l*********8 的大作中提到】
: 输入的图是怎么存储的？ 还要实现图的数据结构吗？
|
Y********f
发帖数: 410 | 7 这个用Vector+set更好吧，每个color是vector的一个元素，这个元素是一个set，包含
所有和该color对应的color
【在 l*********8 的大作中提到】
: My two cents:
: 遍历所有边，把color-color relations 存在multimap里面。
: 最后扫描multimap找出relation最多的color.
|
p*****2
发帖数: 21240 | 8
对了。忘记说了，color的颜色不是连续的。也就是说可能是1,500, 2000, 70000这样
子的。
【在 Y********f 的大作中提到】
: 这个用Vector+set更好吧，每个color是vector的一个元素，这个元素是一个set，包含
: 所有和该color对应的color
|
