본문 바로가기 메뉴 바로가기

ACM-ICPC 상 탈 사람

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

ACM-ICPC 상 탈 사람

검색하기 폼
  • 분류 전체보기 (360)
    • 서버 관련 (9)
      • JS (5)
      • AmazonWebService (1)
      • Backend 지식 (3)
    • 일상 (13)
      • Daliy (1)
      • 잡담 (10)
      • 개인 (2)
    • 알고리즘 관련 (337)
      • BOJ (303)
      • UVaOJ (8)
      • SPOJ (1)
      • 알고리즘&이론 (25)
  • 방명록

코사라주 알고리즘 (2)
SCC(Strongly Connected Component)

방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에..

알고리즘 관련/알고리즘&이론 2017. 1. 21. 20:31
BOJ)2150 Strongly Connected Component

문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo..

알고리즘 관련/BOJ 2017. 1. 21. 18:34
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
  • 이분 그래프(bipartite grape⋯
Total
308,370
Today
42
Yesterday
189
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • 플로이드 워셜
  • Suffix Array
  • 라인 스위핑
  • 이분 매칭
  • SCC
  • MST
  • 네트워크 플로우
  • 힙
  • lca
  • 그리디 알고리즘
  • lazy propagation
  • BFS
  • 다익스트라
  • 디닉
  • 분할 정복
  • 수학
  • 좌표 압축
  • brute force
  • partial sum
  • 에라토스테네스의 체
  • 다이나믹 프로그래밍
  • MCMF
  • LCP array
  • 트리
  • 이분 탐색
  • KMP
  • disjoint-set
  • 위상 정렬
  • dfs
  • 세그먼트 트리
more
«   2021/01   »
일 월 화 수 목 금 토
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
글 보관함
  • 2020/05 (2)
  • 2020/04 (6)
  • 2020/03 (1)
  • 2018/07 (4)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바