11주차

Yes? s → t로 가는 길이 있으면 가능함을 보이면 됨

$(s, a_1, a_2, \dots, a_k, t)$ 의 수열에서, 인접한 두 정점 사이에 간선이 존재해야 함 ($s=t$의 경우에도 길이 있는 것, yes)

 

 

 

no라고 하자 (귀류법), 즉 $t$가 방문되지 않았다. 경로를 따라가다가 최초로 방문되지 않은 노드가 있다. 이를 $a_i$라고 하면, $a_{i-1}$과 $a_i$를 잇는 간선이 존재함에도 불구하고 방문하지 않을 수 없다(알고리즘에서 기계적). 따라서 모순이므로, $t$는 방문돼야 하고, 정답은 yes

 

while box is not empty:
	take one node from box O(m*c)
	if not not marked:
		mark node, O(n)
		computation with node O(n*c), 대체로 상수
		put every adjacent node into box O(m*c)

t가 X라면 그전에 x있어야함, 그뒤에거가 BOX에들어가서 다뽑을때까지 돔, 마킹안되어있으면 마킹해야함

 

yes -> 길이있다.

 

길이없으면 => No

 

덩어리 : 덩어리안의노드들은 어디로든갈 수 있음

 

 

Any-order traversal을 component 개수만큼 돌려야 함

하나의 그래프에서 많은 query를 빠르게 처리할 수 있다. $s_i, t_i$이 서로 같은 Component에 속하는지.

 

덩어리마다 같은 번호를 매겨서 s,t가 같은 번호면 O

 

상수시간에 계산가능 (Rech~)

 

엣지하나당 노드는 무조건두개(2*m)물론, 중복포함해서

 

다익스트라보다 넓은개념 ==> 다익스트라의 일반화 느낌(변수)

 

인접한 노드를 보고, 마크안된거 다골라놓고, 하나씩 재귀를 하면 X, 재귀직전에 체크해야함

 

DFS-Tree ==> graph traversal 해결가능

 

전진한애들만 가지고 만들면 Tree가 나옴