en.md

Light OJ - 1003 : Drunk

---

Problem Summary

---

In this problem,

• Your goal is to find out if it is possible to get drunk.
• To get drunk you will have to maintain m prerequisites.
• In each prerequisite, You will be given two drinks a and b. To get drunk succcessfully you have to take a before having b.
• Now, to get drunk, You must take all the drinks and also by maintaining all the prereqisites.

Hint

---

Try to think in which case you will not be able to get drunk.

Main Idea

---

If the prerequisite says that:

You have to take <soda> before <wine> ,
              <wine> brfore <water> also
              <water> before <soda>

then it will not be possible because it creates a cycle of order and you cannot satisfy all the prerequisite in a cycle. So, You can only be drunk if the prereqisite do not create a cycle.

Detailed Solution

---

So, we what we need to do is:

• Make a graph of dependencies and store them.
• Use DFS algorithm to visit the graph and color them accordingly on the way.
• Whenever you find a cycle using the colors close all the process and print it is not possible to get drunk.
• Otherwise it is possible to get drunk.

Code

C++

// defining dfs colors
#define white 0 // not visited
#define gray 1  // processing 
#define black 2 // done processing


map < string , vector < string > > child; // to store the dependencies
map < string , int > colors; // to store the colors of the nodes
bool drunk; // tells if it can be drunk or not

void dfsCycleFinder(string parent){
	colors[parent] = gray; // started processing
	for(auto nodes : child[parent]){
		// white means not processed yet
		if(colors[nodes] == white) dfsCycleFinder(nodes);
		else if(colors[nodes] == gray){
			// gray to gray in a directed graph
			// which means it has a cycle
			// if it has a cycle one cannot be drunk
			drunk = false;
			return;
		}
	}
	// finished processing
	colors[parent] = black;
}

// returns true if it is possible to get drunk
bool isDrunk(){
	string a, b; // one must have "a" before having "b".
	int m; // number of prereqisite
	cin >> m;
	for(int i = 0 ; i < m ; i++ ){
		cin >> a >> b; // must have a before b
		child[a].push_back(b);
		colors[a] = colors[b] = white; // not visited

	}
	drunk = true; // assuming one can get drunk

	for(auto node: colors){
		if(node.second == white) dfsCycleFinder(node.first);
		if(!drunk) return false; // cannot get drunk
	}
	return true; // can get drunk
}

Written by: Md. Mehrajul Islam