본문 바로가기

라이브러리/그래프4

BFS #include using namespace std; typedef long long ll; typedef pair pii; int R, C; int board[100][100]; int dir8[2][8]{ {0, -1, 0, 1, -1, -1, 1, 1}, {1, 0, -1, 0, 1, -1, -1, 1} }; bool dup[100][100]; void bfs(pii init) { int cr, cc, nr, nc; queue que; dup[init.first][init.second] = true; for (que.push(init); !que.empty(); que.pop()) { tie(cr, cc) = que.front(); for (int i = 0; i < 4; ++i) { nr = cr.. 2020. 12. 13.
Topological Sort #include using namespace std; const int MAX = 10000 + 1; vector adj[MAX]; queue Q; int N, res; int indegree[MAX], cost[MAX], result[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > cost[i]; int K; cin >> K; for (int k = 1; k > p; adj[p].push_back(i); } if (indegree[i] == 0) { Q.push(i); result[i] = cost[i]; res = max(res, result[i]); } } for (int.. 2020. 9. 16.
Dijkstra struct Dijkstra { ll INF = 1e16; int cap; vector dist; vector adj; Dijkstra(int N) { cap = N+1; dist.resize(cap, INF); adj.resize(cap); } void addEdge(int u, int v, ll w) { adj[u].push_back({ w, v }); } void build(int base) { priority_queue que; que.push({ 0LL, base }); dist[base] = 0LL; ll cw, nw; int cn, nn; while (!que.empty()) { tie(cw, cn) = que.top(); que.pop(); if (dist[cn] < cw) continue.. 2020. 8. 6.
Tree #include using namespace std; typedef long long ll; const int MAX = 100001; int parent[MAX]; struct Tree { int root, size; vector child[MAX], edge[MAX]; Tree() { root = -1; size = 0; } Tree(int n) { root = -1; size = n; } void addEdge(int u, int v) { edge[u].push_back(v); edge[v].push_back(u); } void build(int id) { if (root == -1) root = id; for (int next : edge[id]) { if (!parent[next]) { pare.. 2020. 8. 6.