
DISCUSSION
What is good about DFS is that there are many examples if using it among TopCoder problems. Almost all problems of graph theory can be used here. But taking complex algorithms as examples is pretty senselessly, so I will try to talk about problems, where main part of algorithm and implementation is DFS.
First example is Marketing Problem. Problem is in how many ways we can divide goods between adults and teenagers. Some goods can’t be for the same group(like desktop computers and laptops for one group is too much), we will connect such vertices by edges. What do we do is just try to color all vertices into two colors (black and white), so that adjacent vertices have to be of different color. If we can do that we count number of components and return 2 in the power of this number. It is right because if component can be colored into two colors, we can color it in two different ways (it is obvious). So we have two problems: 1)How to color all vertices in that way. 2)How to count number of components.
If we want to color all vertices into two colors (for example color 0 and color 1, there is what we do: we create array color[], where color[i] is color of ith vertex. In the very beginning all vertices’ color is 1, and then we one by one call dfs with vertex if its color is 1. Dfs colors the vertex and calls dfss to color its neighbors with another color. But if any neighbor is already colored with wrong color means that it is impossible to color vertices into two colors: there is no solution. If solution exists (while first stage we faced no problems), we just count number of components as it was explained.
class Marketing
{
public:
//graph presentation: if there is an edge a<>b, then g[a][b] = 1 and g[b][a] = 1;
vector<vector<int> > g;
// if a vertex a is visited, then visited[a] = 1; else visited[a] = 0
vector<int> visited;
//number of vertices
int n;
bool dfs(int v, int c)//v is vertex id and c is the color in which we will paint this vertex
{
visited[v] = c;
for(int i = 0; i < n; i++)
if(g[v][i])//is there is an edge between vertices v and i
{
//if vertex i is already visited and colored in wrong color it is bad and it is impossible to color whole graph
if(visited[i] != 1 && visited[i] == c)
return false;
//if vertex i is not visited we call dfs from it and if returns false we return false too
if(visited[i] == 1 && !dfs(i, 1c))
return false;
}
return true;
}
long long howMany(vector <string> c)
{
n = c.size();
g = vector<vector<int> > (n, vector<int> (n));
visited = vector<int> (n, 1);
//extracting information about graph from input data to fill g  our presentation of graph
for(int i = 0; i < n; i++)
{
istringstream is(c[i]);
int a;
while(is >> a)
{
g[i][a] = 1;
g[a][i] = 1;
}
}
//k is number of components in graph
int k = 0;
for(int i = 0; i < n; i++)
{
if(visited[i] == 1)
{
if(!dfs(i, 0)) // if it is impossible to color graph we return 1 (No solution)
return 1;
k++;
}
}
return (1LL << k);
}
};
Another example of using DFS among TopCoder problems is Circuits. We are given an acyclic graph and we have to return length of the longest path in the graph. Special thing about this problem, which allows using DFS in solution, is that fact, we are given acyclic graph. As we need to find the longest path in it, we just will call DFS from each of vertices, while DFS will return length of maximal path from current vertex. Here is implementation:
class Circuits
{
public:
// our presentation of graph: g[i][j] = 1 if there is no edge i > j else g[i][j] is its weight(or length)
vector<vector<int> > g;
// number of vertices
int n;
// v is vertex's id and father is id of vertex we came from(not to go to it again)
int dfs(int v, int father)
{
int maxi = 0;
for(int i = 0; i < n; i++)
//if it is not father and there is an edge we check if it is longer than current result
if(i != father && g[v][i] != 1)
maxi = max(maxi, dfs(i, v) + g[v][i]);
return maxi;
}
int howLong(vector <string> connects, vector <string> costs)
{
n = connects.size();
g = vector<vector<int> > (n, vector<int> (n, 1));
// extracting data from input
for(int i = 0; i < n; i++)
{
istringstream iscon(connects[i]);
istringstream iscos(costs[i]);
int id, w;
while(iscon >> id && iscos >> w)
g[i][id] = w;
}
int maxi = 1;
for(int i = 0; i < n; i++)
{
fill(used.begin(), used.end(), false);
maxi = max(maxi, dfs(i, 1));
}
return maxi;
}
}
