DFS Tutorial | Competitive Programming

Depth First Search (DFS) for a Graph

Basics:

(1)   http://www.shafaetsplanet.com/?p=973.

(2)   https://www.youtube.com/watch?v=oL5J5il9pFg.

(3)   https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/

Problems:

(1)   Unreachable Nodes (Hackerearth).- see bottom of the page

(2)   280 - Vertex (UVa).

(3)   11518 - Dominos 2 (UVa).

(4)   10452 – Marcus (UVa).

(5)   Vjudge: 1.

(6)   DFS variation: Lightoj. A2OJ.

// DFS.cpp

/// (Data Structure: graph, visit)

vector<int> v[30001];

int vis[30001], c=0;

void dfs(int s)

{

    if(vis[s])

        return ;

    vis[s]=1;

    c++;

    for(int i=0;i<v[s].size();i++)

    {

        if(!vis[v[s][i]])

        {

            dfs(v[s][i]);

        }

    }

}