• Use bfs when possible

• Look out for 0-1 before djikstra

• Independent set is a set of vertices, no two of which are adjacent.

• Topsort

• kahn’s algo (when need to preserve order sometimes like UVA 11060, enqueue 0 indegree nodes in a heap process them)
• simple dfs everywhere else
• DFS spanning tree

• Back edge : explored to explored
• Tree edge : explored to unexplored

#### Finding bridges and articulation points⌗

• If some node is an articulation point then none of its descendants have a back-edge to any of its ancestors . In case it doesn’t have any ancestors (when it is root node) then it shouldn’t have more than 1 children.

• tin[node] : First time we visit node.

• low[node] : lowest tin[] reachable in subtree of node

• For articulation point : $low[child]\geq tin[node]$

• For bridge : $low[child] > tin[node]$

• ##### Implementation:⌗
void dfs(int node,int p=-1)
{
vis[node]=1;
tin[node]=low[node]=timer++;
int children=0;
{
if(u==p)continue;
if(vis[u])low[node]=min(low[node],low[u]);
else
{
children++;
dfs(u,node);
low[node]=min(low[node],low[u]);
if(low[u]>=tin[node] and p!=-1)
{
//found articulation point
}
}
}
if(p==-1 and children>1)
{
//found articulation point
}
}

• In many SCC problems look for property of indegree 0 vertices first.

• Condensed graph is when we substitute SCC with a representative node.

#### Biconnectivity⌗

• Graph is biconnected if it has no articulation points
• Biconnected component : Maximal biconnected subgraph
• Edge biconnected if no bridges
• Vertex biconnected if no articulation points
• In edge biconnected graph an edge will either be bridge or part of a biconnected component. If we denote that component with a single node we’ll get a tree.
• In vertex biconnected graph same kind of condensation gives a block-cut tree i.e. block of biconnected component cut vertex then another block followed by a cut vertex and so on.

#### Counting Paths⌗

• If $V$ is adjacency matrix of unweighted graph. Then $V^n$ contains number of paths of $n$ edges between nodes in a graph.