Bridge( 절선 ), Articualtion point( 절점 ) 찾기

임의의 한 지점에서 다른 모든 지점으로 갈수 있는 경로가 있는 양방향 그래프  G가 있다고 하자.
G에서 어떤 간선 하나가 삭제 되었을 때 G가 2개이상의 그래프로 분리된다면 이 간선을 절선(Bridge) 이라고 한다.

G에서 어떤 정점 v가 삭제 되었을 때(v에 연결된 모든 간선도 같이 삭제) G가 2개 이상의 그래프로 분리 된다면 이 정점을 절점(Articualtion point) 이라고 한다.

절점과 절선을 구하기 위해 그래프를 트리에 backedge 가 달려 있는 상태로 만들어보자.

----- 그림 추가 예정 ---
즉 무방향 그래프를 방향 그래프로 만들어 준다.


dfn[v] : DFS로 방문된 순서
back[v] :  v에서 시작하여 트리 에지와 하나의 백 에지를 통해 도달 가능한 루트에 가장 가까운 정점의 dfn

process :
1. 처음으로 정점 v를 방문하는 경우:
 back[v] = dfn[v]로 초기화

2. 백 에지(v,w) 를 만나는 경우 :
back[v] = min( back[v], dfn[w] )

3. 트리 에지 (v,w)를 만나는 경우 :
back[v] = min( back[v], back[w] )

정점 v가 절점이기 위한 필요 충분 조건
1. 자식을 2개 이상 갖는 루트
2. dfn[v] <= back[w] 인 자식 노드 w가 있는 경우

간선 (v-w)가 절선이기 위한 필요 충분 조건
1. v가 부모 노드이고 w가 자식 노드 일 때 dfn[v] < back [w]

절점 이용 문제 : 병원균퇴치 : http://koistudy.net/?mid=prob_page&NO=1044&SEARCH=0
절선 이용 문제 :  공중도시(KOI 2015 지역본선 고등) : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2127%20&sca=50

Kosaraju's algorithm (strongly connected component)

Strongly Connected Componet, 줄여서 SCC는 단방향 그래프에서 사이클이 생겨 각 각의 지점에서 다른 각 각의 지점으로 갈 수 있을 때 하나의 집합 또는 이를 찾는 알고리즘을 통칭한다.

SCC는 단방향 그래프에서 DAG로 바꿔서 문제를 풀 때 유용하다.

SCC 중 kosarju's algorithm은 구현도 쉽고 시간 복잡도도 O(N) 이다.

1. 순서는 상관 없이 한 정점에서 시작하여 DFS로 방문하지 않은 모든 정점을 방문한다. 각 정점에서 DFS가 자신에게 돌아왔을 때 증가된 번호를 매겨 준다.

2. 모든 간선의 방향을 바꾸고 아직 방문 하지않고 매긴 번호가 큰 정점부터 rDFS(방향 바뀐 간선을 이용)를 시작하는 데 시작하는 정점에서 갈 수 있는 모든 정점들이 하나의 같은 컴포넌트 이다.

SCC 연습 문제 :Traveling Ship : http://koistudy.net/?mid=prob_page&NO=503&SEARCH=0

현금 인출기(APIO 2009) : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1683&sca=50&sfl=wr_subject&stx=%ED%98%84%EA%B8%88&sop=and

APIO 2016 Boat 보트 풀이

구사과의 boat 풀이 : http://koosaga.myungwoo.kr/entry/APIO-2016
 
boat를 채점가능한 온라인 저지
정올 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2278&sca=50
코이스터디 : http://koistudy.net/?mid=prob_page&NO=1493&SEARCH=0
백준 : https://www.acmicpc.net/problem/12735



DP[i][j] 를 i


문제를 보고 풀이를 생각하다보면 combination을 써야함은 확실할 것이다.
------------------------수정 중 ------------------------------------

2016.11.26 정보 주말 프로그램

풀이 출처 : http://koistudy.net/?mid=free&document_srl=169669
A,B pass

C. Prob No. 069A : 젖소 길 건너기 [CH04.3. USACO(Bronze)]
http://koistudy.net/?mid=contest_prob_page&NO=1690&ContestID=50c3d7614917b24303ee6a220679dab3


ai와 bi를 pair로 묶어 sort를 하면 ai가 오름 차순으로 정렬된다. 충돌을 하지 않는 소의 후보가 될 수 있는 것은
1부터 현재 i번째 소까지 볼때 b1~bi-1보다 bi 값이 큰 갱신되는 소이다.
그 후보에 대하여 스택을 이용하여 k:[i+1,n]에서 bi보다 작은 bk가 없는지 본다.
스택에 push,pop이 한 번씩 되므로 O(n) 이다.

#include <bits/stdc++.h>
#define N 100005
#define INF 987654321
using namespace std;
pair<int,int> s[N];
stack<int> S;
int n,a[N],b[N];
int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        s[i].first=a[i];s[i].second=b[i];
    }
    sort(s+1,s+1+n);
    int mx=-INF;
    for(i=1;i<=n;i++){
        if(mx<s[i].second) S.push(s[i].second),mx=s[i].second;
        else{
            while(!S.empty()){
                if(S.top()>s[i].second) S.pop();
                else break;
            }
        }
    }
    printf("%d",S.size());
}

정렬 :  O(nlogn)
stack : O(n)
Prob No. 0196 : 커피 전문점 [CH04.1.Competition(GTPC10)]
http://koistudy.net/?mid=prob_page&NO=406&SEARCH=0

///풀이 설명 : A-B , B-C의 최단 거리위 점들이 후보지가 된다. C-A는 할 필요 없다.

정보 창의력 대회 문제 풀이.

망해버렸다.
총 8문제로 2문제씩 small,large로 되어 있다.

 Prob No. 0681 : 최대약수구간 (Large) [CH02.2.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1665

이런 야비한 방법도 통과할 수 있다는 걸 깨달았다.

#include <bits/stdc++.h>
int mx,i,n,ans,a[50]={0,1,2,6,12,24,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640};
int main()
{
    scanf("%d",&n);
    for(i=1;i<=45;i++)
        if(n>=a[i])
            mx=a[i];
    printf("%d",n-mx+1);
}

Prob No. 0686 : 24시간 마법진 (Large) [CH02.4.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1670
걍 nC4 구하라는 문제

2016.11.19 정보 주말 프로그램

주프 풀이 정리 : http://koistudy.net/?mid=free&document_srl=169292

A. Prob No. 00F8 : 저녁 식사 줄서기 [CH03.2.USACO(Bronze)]
http://koistudy.net/?mid=prob_page&NO=248

걍 앞에서부터 1갯수 세고 뒤에서부터 2갯수 세서 합이 최소인 곳이 정답

B. Prob No. 01F2 : 무단 외출 [CH03.2.USACO(Bronze)]
http://koistudy.net/?mid=prob_page&NO=498

쉽다.

C. Prob No. 07D8 : 금강산 [CH03.2.USACO(Bronze)]
http://koistudy.net/?mid=prob_page&NO=2008
flood fill로 영역 나누고 주변에 대해 한 곳이라도 높은 곳이 없으면 봉우리다.

D. Prob No. 0699 : 역삼각 수 놀이 [CH02.4.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1689

nCr=nCn-r 인 점에 착안하여 값이 같은 두개 씩 정해주면서 재귀 돌리면 된다.
O(n*n!/(2^n/2))

E. Prob No. 0448 : SNS의 친구들 [CH03.4.USACO(Gold)]
http://koistudy.net/?mid=prob_page&NO=1096

하나씩 각 각에 대해 그래프가 성립하는지 판단, 차수가 가장 높은 정점부터 지우고, 지운거 차수에서 빼고 다시 가장 높은 정점부터 빼가는 과정 반복
O(N^2logN)

F. Prob No. 0696 : 타일 채우기 5 [CH02.2. Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1686
공부하자

2016.11.07 정보과학 주말 프로그램 풀이

Prob No.0689 : 스터디 [CH02.2. Algorithm(Design)]
S에서 시작하는 2개의 다익스트라를 돌리면 된다.
첫번째 다익스트라는 S에서 시작하는 정상적인 다익스트라를 돌리고
두번째 다익스트라는 간선의 방향을 반대로해서 S에서 시작하는 다익스트라를 돌린다.

첫번째와 두번째 거리 합 중 가장 작은 것이 정답이 된다.
O(NlogN+M)

Prob No.068A : 시간여행 [CH02.2. Algorithm(Design)]
모든 정점의 값을 0으로 하고, 벨만-포드 돌려서 n번째에도 값이 갱신이 되면 음수 사이클이 존재. 벨만 포드의 정의와 관련 지어 생각하면 쉽다.
for(1~정점 수)
   for(1~간선 수)

O(NM)