-
[BOJ] 2152 : 여행 계획 세우기
2152 : 여행 계획 세우기 풀이 주어진 그래프에서 scc를 구해서, 각 컴포넌트를 노드로 하는 새로운 그래프를 만들자 scc로 구성된 그래프는 항상 DAG이다 여기서 위상정렬 같은 느낌으로 dp? 같은 느낌으로 으쌰으쌰 하자 타잔으로 scc를 구하면 위상정렬의 역순으로 컴포넌트를 구하게 된다 아몰랑 코드 #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int MAXN = 1e4 + 10; int n, m, s, e; int cnt, pos, scc[MAXN], chk[MAXN], stk[MAXN]; vi gph[MAXN]; vector<vi> res; int dfs(int now) {...
-
[BOJ] 10265 : MT
10265 : MT 풀이 , 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; using vi = vector<int>; const int n_ = 1e3 + 1; int n, k; int a[n_], vst[n_], cyc[n_], scc[n_], dph[n_], dp[n_]; vector<int> b[n_]; int c_dfs(int now, int dep, int num) { vst[now] = num, dph[now] = dep; if (vst[a[now]] == num) return dph[now] - dph[a[now]] + 1; return c_dfs(a[now], dep + 1, num); } int s_dfs(int now, int num) {...
-
[BOJ] 2150 : Strongly Connected Component
2150 : Strongly Connected Component 풀이 scc를 구현하자! 다른 블로그에 좋은 scc 설명이 많으니까 나는 구현만 해야겠다 원래 stl stack 써서 짰는데 메모리 많이 먹길래 기분 나빠서(?) 배열로 바꿨다. 처음 코드가 타잔, 다음 코드가 코사라주이다. 코드 타잔 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vi; const int v_ = 1e4 + 1; int v, e, cnt, pos, scc[v_], chk[v_], stk[v_]; vi gph[v_]; vector<vi> res; int dfs(int now) { chk[now] = ++cnt;...