• 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;
        for(int u:adj[node])
        {
            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.