(알고리즘) 그래프

보통  인접행렬 :O(V^2)
        연결리스트: O(E)을 사용하는데,
이 두개가 무의미해지는 상황이 있다.


이럴 경우는 간선을 저장하는 간선리스트를 만든다.


E[0]= 1 2
E[1]= 1 5
......
E[15]=0 4



이때 간선 0번째의 의미는 정점 1과 2를 연결하는 간선이라는 의미다
그러므로 int E[][]=new int[간선의 갯수][2]가 된다.


이를 시작정점이 몇개인지에 해당하는 배열에 저장하면
for(in i=0;i<M;i++){
  cnt[E[i][0]]+=1;
}

즉 cnt[1]이 2라면 1에서 시작하는 간선의 갯수가 2개라는 의미이다.

이를 누적하면

for(int i=1;i<=N;i++){
  cnt[i]=cnt[i-1]+cnt[i];
}

여기서 알 수 있는 것은  i번쨰 정점과 연결된 간선은 cnt[i-1]부터 cnt[i]-1까지이다.
왜냐면 누적값이므로..

즉 3번정점과 연결된 간선은 cnt[2]~cnt[3]-1
    4번정점과 연결된 간선은 cnt[3]~cnt[4]-1