BFS-based topological sort

11060.cpp

#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <functional>
#include <cstring> //memset
using namespace std;

bool visited[110];
int N,M,T;

vector<string> beverages;
vector<int> in; //in degree
map<string, int> mp;
vector<vector<int>> adj_list; 

int main(){
	string ln;
	T=1;
	while(getline(cin, ln)){
		beverages.clear();
		mp.clear();
		in.clear();
		
		if(ln=="") continue;
		sscanf(ln.c_str(), "%d", &N);
		adj_list.assign(N, vector<int>()); 
		in.assign(N, 0);
		for(int i=0;i<N;++i){
			string b;
			cin>>b;
			beverages.push_back(b);
			mp[b]=i;
		}
		cin>>M;
		for(int i=0;i<M;++i){
			string b1, b2;
			cin>>b1>>b2;
			in[mp[b2]]+=1;
			adj_list[mp[b1]].push_back(mp[b2]); 
		}

		memset(visited, 0, sizeof(visited));
		priority_queue<int, vector<int>, greater<int>> q; //keep the order, same level print appear frist in the input
		cout<<"Case #"<<T++<<": Dilbert should drink beverages in this order:";

		/* modified BFS topological sort */
		for(int i=0;i<in.size();++i){
			if(in[i]==0){  //push v with in-degree 0
				visited[i]=true;
				q.push(i);
			}
		}

		while(!q.empty()){
			int u = q.top();q.pop();
			cout<<" "<<beverages[u];
			for(auto it=adj_list[u].begin(); it!=adj_list[u].end();it++){
				int v = *it;  
				in[v]-=1;    //reduce in-degree of all it's neighbor
				if(!visited[v] && in[v]==0){
					visited[v]=true;
					q.push(v);
				}
			}
		}
		cout<<".\n\n"; //After each test case you must print a blank line. WA because of this!
	}
	return 0;
}

/* Can't use DFS-based topological sort here since transitive 
 * property for vertex requiring all in-degree 0 comes before
*/
// void dfs(int n){
// 	visited[n]=true;
// 	for(int i=0;i<adj_list[n].size();++i){
// 		int v = adj_list[n][i];
// 		if(!visited[v]){
// 			dfs(v);
// 		}
// 	}
// 	topo.push_back(n);
// }

// DFS
// for(int u=0;u<N;++u){
// 	if(!visited[u])
// 		dfs(u);
// }