본문 바로가기

분류 전체보기327

강한 연결 요소(SCC) 그래프에셔 u->v와 v->u 경로(간선아님)가 모두 있으면 같은 SCC에 속한다고 한다. dfs하면서 stack을 이용해서 분리해 낸다. 선형시간 O(n) 필요한 것: int id = 0, dfsn[MAX]={0}; //방문하는 정점마다 고유번호를 저장하기 위함. dfsn은 visit의 역할도 수행한다. bool finished[MAX] = {false}; //scc추출이 완료된 정점인지 vector adj[MAX] stack s 선택1) vector SCC; 선택2) int SN=0, sn[MAX]; //해당 정점이 포함된 scc번호를 저장함 int id, dfsn[MAX]; bool finished[MAX]; vector adj[MAX]; vector SCC; stack s; int makeSCC(.. 2019. 8. 19.
위상정렬, DAG(Directed Acyclic Graph) 그래프의 분류 중 하나로 DAG,사이클이 없는 방향그래프가 있다. DAG에서는 항상 위상정렬이 가능하고 그 후에 동적 계획법을 적용하는 것이 가능하다. ㅁ 정점u에서 정점v로 가는 최단/최장 경로는 무엇인가? ㅁ 경로 중 간선의 개수가 가장 적은/많은 경우 간선은 몇 개인가? ㅁ 모든 경로에 포함된 정점은 어떤 것이 있는가? ㅁ 서로 다른 경로의 개수는 몇 개인가? 등등.. 위상정렬된 순서대로 처리하면 구할 수 있다. 또한 모든 동적 계획법 문제는 DAG로 나타낼 수 있다. 이 때 정점은 dp상의 상태에, 간선은 상태간의 관계에 대응된다. ex)동전문제, 냅색.. 사이클이 없는 그래프에서 정점의 탐색이 끝난 순서 (fin[u]=true)의 반대 순서로 처리하면 위상정렬 순서 (예)https://suunt.. 2019. 8. 18.
최소 스패닝 트리 크루스칼 O(ElogE) 필요한 것: union-find (merge 병합성공여부 반환) 간선구조체 - 가중치 기준으로 오름차순 정렬하기 위함. int uf[100001]; int find(int a) { if (uf[a] < 0) return a; return uf[a] = find(uf[a]); } bool merge(int a, int b) { a = find(a); b = find(b); if (a == b) return false; uf[a] = b; return true; } struct Edge { int u, v, w; Edge(int u1, int v1, int w1) : u(u1), v(v1), w(w1) {} bool operator < (const Edge& O) const { re.. 2019. 8. 18.
플로이드 와샬 모든 정점간 최단거리를 구해내는 알고리즘 O(V^3) 벨만 포드로 모든 정점간 최단거리를 구하려면 O(V^2 * E) 이므로 벨만포드보다 빠르다. 필요한 것: dist[MAX][MAX] = {입력값 | 연결안됐으면INF} for(int k=0; k 2019. 8. 18.

티스토리툴바