5) судя по личному опыту — применимы, если речь идет о числе обращений до пары миллионов. Сложность везде такая же, как у аналогов из C++ — амортизированное О(1). Также есть вероятность взлома — http://mirror.codeforces.com/blog/entry/4876

Кстати насчет халявной длинки, ее вроде как хотят реализовать в C++14

1) Я знаю лишь три варианта, причём всеобщих, не только на Java. Не считая матрицы смежности, аналогично, это ArrayList g[], и граф через самописные списки с помощью нескольких обычных массивов.

2) Я бы не сказал, что он медленный. У него куча медленных аспектов. Например, многомерные массивы, с ними хоть и удобно работать, но это массивы объектов, едят много памяти и времени. Известный хак — размерности должны быть по возрастанию. То есть new int[2][1000000] лучше, чем new int[1000000][2]. А ещё нельзя (особенно на здесь на cfr) сортировать через Arrays.sort() массивы примитивов, есть анти-Java-Sort тесты, нагибающие стандартную сортировку.

3) По моему личному опыту — без разницы.

4) не понял вопроса

5) Во-первых скажу, что (опять же по опыту) они сильно медленнее аналогов в c++, особенно Map. О HashMap ещё уже кое-что писали, его можно тоже нагнуть по TL.

1) ArrayList<Integer>[] — то же самое, что vector<int> v[100500]. Очень удобно бегать по смежным вершинам: for (int to : graph[from]) { ... }

2) Меньше объектов и все будет нормально.

3) Я бы делал класс, удобнее же. Производительность одинаковая будет.

4) Знатоки терминологии негодуют: создаются объекты, а не классы. Где-нибудь до миллиона объектов обычно влезает в TL.
Наиболее плохо это сказывается в каком-нибудь FFT, где использование класса комплексных чисел раз в 10-15 медленнее, чем два массива double. Все потому, что в FFT O(NlogN) операций с комплексными числами, да еще и с немаленькой константой.

5) На Codeforces, видимо, с недавних пор неприменимы. А на нормальных контестах обычно авторы оказываются нормальными людьми и не делают такие тесты.

6) А зачем? Там и так все понятно. Лучше читать Javadoc у классов из java.util

1) dalex описал удобный способ, но при наличии проблем с TL/ML стоит использовать способ быстрый. А именно: завести массив массивов ребер, потом считать все ребра, потом создать сами массивы ребер и заполнить их. Краткий пример кода (ориентированный невзвешенный граф, на более сложные случаи обобщается без проблем):

int n = sc.nextInt(), m = sc.nextInt();
int[][] graph = new int[n][];
int[] a = new int[m], b = new int[m];
int[] deg = new int[n];
int[] pos = new int[n];
for (int i = 0; i < m; i++) {
    a[i] = sc.nextInt() - 1;
    b[i] = sc.nextInt() - 1;
    deg[a[i]]++;
}
for (int i = 0; i < n; i++) {
    graph[i] = new int[deg[i]];
}
for (int i = 0; i < m; i++) {
    graph[a[i]][pos[a[i]]++] = b[i];
}

2) Про отказ от объектов уже было упомянуто, также при жестком пропихе асимптотически неоптимального кода стоит отказываться и от лишних мелких функций (вызов функции в Java в сравнении с C++ является крайне дорогостоящей операцией — лично читал исходники Java VM). Также стоит записывать в локальные переменные значения выражений, которые используются несколько раз (пример: стоит кэшировать строки двумерных массивов).

Дисклеймер: пример к ответу на первый вопрос я написал только что, причем вслепую.

Возможно, Вам также будет интересна тема "Представление графа списками смежности в Java"