Skip to content

Instantly share code, notes, and snippets.

View NamPE286's full-sized avatar

NamPE286

9 followers · 0 following
View GitHub Profile
@NamPE286
NamPE286 / dsu.cpp
Last active December 3, 2023 22:32
Disjoint Set Union (DSU) C++ implementation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class DSU {
private:
vector<ll> p; // parent if positive, size if negative, parent of root is the size of component
public:
@NamPE286
NamPE286 / segment_tree_iterative.cpp
Last active May 29, 2023 06:44
Segment Tree C++ iterative implementation (only support point update)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segment_tree {
//0-indexed
vector<ll> tree;
ll n;
segment_tree(vector<ll> &nums) {
@NamPE286
NamPE286 / BIT.cpp
Last active November 22, 2022 15:52
Binary Indexed Tree (Fenwick Tree) C++ implementation for range update, point query
// https://cses.fi/problemset/task/1651/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct BIT{
//1-indexed
vector<ll> bit;
ll n;
@NamPE286
NamPE286 / segment_tree_lazy.cpp
Last active March 6, 2023 09:10
Segment tree with lazy propagation C++ implementation (use for range update range query problems)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* @brief A data structure that allow update point/range and query operations efficently
*
*/
template <typename T>
@NamPE286
NamPE286 / euler.cpp
Created December 26, 2022 03:50
Count all coprime with N in range [1,N] (Euler's totient function)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll phi(ll n){
ll res = n;
for(ll i = 2; i * i <= n; i++){
if(n % i == 0){
while(n % i == 0) n /= i;
@NamPE286
NamPE286 / dfs_recursive.cpp
Last active April 16, 2023 06:36
Recursive DFS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dfs(map<ll, vector<ll>> &graph, ll curNode, ll endNode, ll step = 0, set<ll> &visited) {
if (curNode == endNode) return step;
if (visited.count(curNode)) return -1;
visited.insert(curNode);
ll ans = LLONG_MAX;
@NamPE286
NamPE286 / dfs_iterative.cpp
Last active March 1, 2023 04:39
DFS iterative
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll node;
ll step;
};
@NamPE286
NamPE286 / bicoloring.cpp
Last active April 4, 2023 17:48
Bipartite graph bicoloring with DFS
// https://codeforces.com/contest/862/problem/B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void bicoloring(unordered_map<ll, vector<ll>> &graph, vector<ll> &color, ll curNode, ll curColor = 1) {
if (color[curNode]) return;
color[curNode] = curColor;
for (ll i : graph[curNode]) {
@NamPE286
NamPE286 / is_bipartite.cpp
Last active April 4, 2023 18:03
Check if a graph is bipartite using DFS bicoloring
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool is_bipartite(unordered_map<ll, vector<ll>> &graph, vector<ll> &color, ll curNode = 1, ll curColor = 1) {
if(color[curNode]) return true;
color[curNode] = curColor;
bool ans = true;
for(ll i : graph[curNode]){
@NamPE286
NamPE286 / general_tree.cpp
Last active April 16, 2023 12:29
Dynamic general tree class implementation in C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
class general_tree {
private:
T root;
bool modified = false;