Cyclicity in directed graph, coloring technique
All simple cycles in a undirected graph, w/o composite cycles
All tricks using union-find algorithm
Tarjan's algorithm to find articulation points, bridges
Finding transitive closure of a graph using Floyd Warshall
BFS on complement graph if the graph is sparse
Kahn's algorithm for topological ordering
Maximal/Minimal Topological ordering
Floyd Warshall for finding shortest paths
Minimum Spanning Tree, Prim vs Kruskal
Dijkstra's shortest path algoritm for non-negative edges
K-shortest path and ghostness in dijkstra
Use Bellman Ford for negative edge weights
Detect negative cycle using Bellman Ford
Find shortest cycle using BFS and edge deletion
Strongly connected component aka SCC
Kosaraju's algorithm for condensed SCC
void dfs(int u,int p=-1){
vis[u] = 1;
for(auto v:g[u]){
if(v==p) continue;
else if(vis[v]){
cycle_end = u;
cycle_start = v;
return 1;
}
par[v]=u;
if(dfs(v,p[v])) return 1;
}
return 0;
}
vi find_cycle(){
vis.assign(n,0);
par.assign(n,-1);
cycle_start = -1;
for(int v=0;v<n;v++)
if(!vis[v] && dfs(v)) break;
if(cycle_start==-1) cout << "Acyclic" << endl;
else{
vi cycle;
cycle.eb(cycle_start);
for(int v=cycle_end;v!=cycle_start;v=p[v]) cycle.eb(v);
cycle.eb(cycle_start);
reverse(all(cycle));
return cycle;
}
} vi color,par;
bool dfs(int u){
color[u] = 1; // GRAY
for(auto v:g[u]){
if(color[v]==0){ // WHITE
p[v] = u;
if(dfs(u)) return 1;
}
else if(color[u]==1){
cycle_end = u;
cycle_start = v;
return 1;
}
}
color[u] = 2; // BLACK
return 0;
}
Think in terms of DFS Tree! This algorithm does not work for composite cycles.
int parent[N], who[N], color[N];
int cycle = 0;
void dfs(int u,int p=-1){
if(color[u]==2) return;
if(color[u]==1){
cycle++;
int curr = p;
who[cur] = cycle;
while(curr!=u){
cur = parent[cur];
who[cur] = cycle;
}
return;
}
parent[u] = p;
color[u] = 1;
for(int v:g[u]){
if(v==p) continue;
dfs(v,u);
}
color[u] = 2;
}https://www.geeksforgeeks.org/tree-back-edge-and-cross-edges-in-dfs-of-graph/amp/ [Back Edge, Foreward Edge, Cross Edge]
int par[1000], rank[1000];
int root(int u){
if(par[u]==u) return u;
return par[u] = root(par[u]);
}
void Union(int u,int v){
int r1 = root(u), r2 = root(v);
if(rank[r1]>rank[r2]) par[r2] = r1;
else if(rank[r1]<rank[r2]) par[r1] = r2;
else par[r2] = r1, rank[r1]++;
}
Trick 1: If edge deletion, reverse the operations and use union-find
Trick 2: If a vertex is connected to other vertex by two independent type of edges, what is the number of vertex which are connected to it by road and not by rails, say, mp1[root_roads[u]]-mp2[root_roads[u],root_rails[u]]
void dfs(int u,int p=-1){
int branch = 0;
low[u] = disc[u] = ++timer;
for(auto v:g[u]){
if(v==p) continue;
else if(disc[v]) low[u] = min(low[u],disc[v]);
else{
branch++;
dfs(v,u);
if(low[v]>=disc[u]) ap[u] = 1;
low[u] = min(low[u],low[v]);
}
}
if(p==-1 && branch>1) ap[u] = 1;
} void dfs(int u,int p=-1){
low[u] = disc[u] = ++timer;
for(auto v:g[u]){
if(v==p) continue;
else if(disc[v]) low[u] = min(low[u],disc[v]);
else{
dfs(v,u);
if(low[v]>disc[u]) bridges.eb(mp(u,v));
low[u] = min(low[u],low[v]);
}
}
}For undirected graph, use DSU
For directed graph, use Floyd Warshall/DFS
vi d(n+1,-1);
queue<int> q;
set<int> undisc;
q.push(s);
d[s]=0;
for(int i=0;i<=n;i++) if(i!=s) undisc.insert(i);
while(!q.empty()){
int u = q.front();
q.pop();
set<int> temp;
for(auto &v:undisc){
if(g[u].find(v)==g[u].end()){
d[v] = d[u] + 1;
q.push(v);
}
else temp.insert(v);
}
undisc = temp;
}DFS method
stack<int> s;
void dfs(int u){
vis[u] = 1;
for(auto &v:g[u]){
if(!vis[v]) dfs(v);
}
s.push(u);
}
void all_topo(int mask){
bool flag = true;
for(int u=0;u<V;u++){
if(!in[u] && !(mask&(1<<u))){
for(auto v:g[u]) in[v]--;
res.eb(u);
mask^= 1<<u;
alltopo(mask);
mask^= 1<<u;
res.erase(res.end()-1);
for(auto v:g[u]) in[v]++;
flag = false;
}
}
if(flag)
for(int i=0;i<sz(res);i++) cout << res[i] << " ";
cout << endl;
} void topo_sort(){
vi in(V,0);
for(int u=0;u<V;u++){
for(auto v:g[u]) in[v]++;
}
queue<int> q;
for(int u=0;u<V;u++) if(!in[u]) q.push(u);
int cnt = 0;
while(!q.empty()){
int u = q.front();
q.pop();
cout << u << " " ;
for(auto v:g[u]) if(--in[v]==0) q.push(v);
cnt++;
}
assert(cnt==V);
} Min Topological Ordering: Topological Sorting is lexicographically smallest, idea: normal Kahn, in[], pick lex smallest vertex everytime
Min Topological Labelling: Topological labelling is lexicographically smallest, idea: reverse Kahn, out[], pick lex largest vertex everytime and place it in the front
void floyd(){
for(int k=0;k<V;k++){
for(int i=0;i<V;i++){
for(int j=0;j<V;j++){
chmin(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
} // Prim: idea, Among all the reachable vertex choose the cheapest one.
using minheap = priority_queue<pii,vector<pii>,greater<pii>>;
ll prim(int u){
minheap q;
ll ans = 0;
q.push(mp(0,u));
while(!q.empty()){
pii u = q.top();
q.pop();
if(vis[u.se]) continue;
ans+=u.fi;
vis[u.se]=1;
for(auto &v:g[u.se]){
if(!vis[v.fi]) q.push(mp(v.se,v.fi));
}
}
return ans;
} // kruskal: idea, Among all edges which can be added choose the one min val
void kruskal(){
sort(all(e));
ll ans = 0ll;
for(int i=0;i<sz(e);i++){
int u = e[i].se.fi;
int v = e[i].se.se;
int ru,rv;
ru = root(u);
rv = root(v);
if(ru!=rv){
ans+= e[i].fi;
Union(u,v);
}
}
cout << ans << endl;
}-
Some-times if dependency of some edge is given, then you can use edges as vertices for MST/dijkstra -
Very important dijkstra trick: Dijkstra can be used as dynamic programming strategy where the substructure is implicit -
Min Spanning Tree has O(MlogM) for sorting the edges complexity, But if you get a mst adding a new edge can only change the number of edges in MST by at most 1 in O(N) operation- Idea: Maintain a sorted edge list with MST edges so far.
- Add new edge. Either it connects or creates a new cycle.
- Either way we need a way to get the new MST in O(N).
- Connecting is easy but breaking a cycle is tedious.
- So sort the new list in O(N), sorting an already sorted list + 1 extra edge. ~ N edges.
- Go through the sorted list again and create the MST. O(N).
https://codeforces.com/contest/76/problem/A https://atcoder.jp/contests/abc164/tasks/abc164_e
void dijkstra(int u){
for(int i=0;i<N;i++) d[i] = inf;
d[u] = 0;
priority_queue<pii,vector<pii>,greater<pii>> q;
q.push({0,u});
while(!q.empty()){
pii u = q.top();
q.pop();
if(d[u.se]!=u.fi) continue;
for(auto &v:g[u.se]) if(chmin(d[v.se],d[u.se]+v.fi)) q.push(mp(d[v.se],v.se));
}
}https://cses.fi/problemset/task/1196/
const int N = 1e5+5;
ll n,m,k;
vector<pair<ll,ll>> g[N];
ll ghostness[N];
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for(int i=0;i<m;++i){
ll a,b,c; cin >> a >> b >> c;
g[a].eb(b,c);
}
for(int i=1;i<=n;++i) ghostness[i] = k;
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;
q.push(mp(0ll, 1ll));
vector<ll> kshort;
while(!q.empty()){
auto u = q.top();
q.pop();
if(ghostness[u.se]>0ll){
if(u.se == n) kshort.eb(u.fi);
ghostness[u.se]--;
for(auto v: g[u.se]){
q.push(mp(u.fi + v.se, v.fi));
}
}
}
output_vector(kshort);
return 0;
} void bellman(int u){
for(int i=0;i<N;i++) d[i] = inf;
d[u] = 0;
while(1){
bool opt = 0;
for(int i=0;i<m;i++){
auto [w,a,b] = e[i]; // tuple
if(d[a]+w < d[b]){
d[b] = max(-inf,d[a]+w);
p[b] = a , opt = 1;
}
}
if(!opt) break;
}
} bool bellman(int u){
for(int i=0;i<N;i++) d[i] = inf;
d[u] = 0;
bool opt = 0;
for(int i=1;i<=N;i++)
opt = 0;
for(int i=0;i<m;i++){
auto [w,a,b] = e[i]; // tuple
if(chmin(d[b],d[a]+w)) p[b] = a , opt = 1;
}
}
if(opt) return 1;
return 0;
}https://codeforces.com/contest/1817/problem/B
bool bfs(int a, int b){
queue<int> q;
q.push(a);
vi parent(n+3,-1);
vector<bool> vis(n+3,0);
parent[a] = -1;
vis[a] = true;
while(!q.empty()){
auto u = q.front();
q.pop();
// check if the shortest cycle is formed.
if(u==b){
fish.clear();
unordered_set<int> cycle;
cycle.insert(b);
fish.eb(a,b);
while(u!=a){
fish.eb(u,parent[u]);
u = parent[u];
cycle.insert(u);
}
int c=0;
for(int f: g[a]){
if(cycle.find(f) == cycle.end()){
c++;
fish.eb(f,a);
}
if(c==2){
return true;
}
}
return false;
}
for(int v: g[u]){
if((u==a && v==b) || (v==a && u==b)) continue; // delete this edge
if(v==parent[u]) continue;
if(!vis[v]){
vis[v] = true;
parent[v] = u;
q.push(v);
}
}
}
return false;
}
void bfs_01(int s){
for(int i=0;i<N;i++) d[i] = inf;
d[s] = 0;
deque<int> q;
q.push_front(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(auto &[v,w]:g[u]){
if(chmin(d[v],d[u]+w)){
if(w==0) q.push_front(v);
else q.push_back(v);
}
}
}
}Problems: https://codeforces.com/contest/1063/problem/B [Nice]
vi g[MaxN],gr[MaxN];
vb vis[MaxN];
stack<int> s;
vi component;
void dfs1(int u){
vis[u] = 1;
for(auto v:g[u]) if(!vis[v]) dfs1(u);
s.push(u);
}
void dfs2(int u){
vis[u]=1;
component.eb(u);
for(auto &v:gr[u]) if(!vis[v]) dfs2(u);
}
void kosaraju(){
vis.assign(MaxN,0);
for(int i=0;i<n;i++) if(!vis[i]) dfs1(i);
vis.assign(MaxN,0);
while(!s.empty()){
int u = s.top();
s.pop();
if(!vis[u]) dfs2(u);
// .....got the component.....
component.clear();
}
} vi g_scc[MaxN], root[MaxN];
vi A;
void build(){
while(!s.empty()){
int u = s.top();
s.pop();
if(!vis[u]) dfs2(u);
int r = component.front();
for(auto v:component) root[v] = r;
A.eb(r);
component.clear();
}
for(int u=0;u<n;u++){
for(auto &v:g[u]){
int r1 = root[u], r2 = root[v];
if(r1!=r2) g_scc[r1].eb(r2); // building compressed scc
}
}
}