인접리스트를 이용한 그래프

1. 정점과 간선수가 많아지면 인접행렬은 비효율적.

2. ArrayList를 사용하여 그래프를 표현.

ex) 5개 정점, 9개의 간선

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

 

[1] -> 2 -> 3 -> 4

[2] -> 1 -> 3 -> 5

[3] -> 4 

[4] ->2 ->5

class Main {

	static int n,m;		
	static int [] ch;//중복 방지용 : 한번 지나간 정점은 다시 찾지 않는다.(무한루프 방지)
	static ArrayList<ArrayList<Integer>> graph; // 인접 리스트 생성.
	static int answer;
	public void DFS( int v) {
		if( v == 5) {
			answer ++;
		} else {
			
			for( int nv : graph.get(v) ) {
				if( ch[nv] == 0) {
					ch[nv]=1;
					DFS(nv);
					ch[nv]=0;
				}
			}
			
			
		}
	}
	
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		ch = new int[n+1];
		graph = new ArrayList<>();
		for ( int i = 0 ; i <= n ; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		for ( int i = 0 ; i < m ; i++) {
			graph.get(in.nextInt()).add(in.nextInt());
		}
		
		//인접리스트 출력
		int idx= 0;
		
		for ( ArrayList<Integer> a : graph) {	
			System.out.print("[ " +idx+ "]");
			for (int e : a) {
				System.out.print(e + " ");	
			}
			System.out.println();
			idx++;
		}
		
		//1번 정점에서 출발
		ch[1]=1;
		M.DFS(1);
		System.out.println(answer);
	}
}


ex)
input
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

output
[ 0]
[ 1]2 3 4 
[ 2]1 3 5 
[ 3]4 
[ 4]2 5 
[ 5]

6