BFS/DFS part - 1

BFS/DFS কি , কিভাবে কাজ করে এই ব্যাপারে আমি আর কিছু লিখতে যাচ্ছি না । অনেক ভাল ব্লগ লেখা হইছে এইটা নিয়ে । এইখানে আমার ইচ্ছা BFS/DFS দিয়ে কিছু interesting problem কিভাবে সল্ভ করা যায় এর solve ট্রিক্স লিখে রাখা । যদি কারো এই এল্গরিথম নিয়ে কোন আইডিয়া না থাকে তাহলে নিচের লিঙ্ক থেকে দেখে নিতে পারে ।

1. BFS 
2. DFS    
3. youtube  

যারা একদমই নতুন নতুন BFS/DFS শিখেছে তাদের এই জন্য লিখাটা খুব একটা উপকারি হবে না । আমি চেস্টা করছি কিছু interesting problem এর solution process বলার জন্য ।

Xor-Tree ::
এই প্রবলেম এ বলা হইছে আমাদের একটা tree input দেওয়া হবে । প্রাথমিক ভাবে এর কোন নোডে কি কি ভ্যালু আছে ( ভ্যালু শুধু মাত্র ১/০ ) আছে তাও দেওয়া আছে । আমাদের একটা টার্গেট প্রসেস এ যাইতে হবে । এইখানে আমরা  কিছু কাজ করতে পারি ।

1.  আমরা চাইলে কিছু নোড এর ভ্যালু ফ্লিপ করে দিতে পারি ( মানে এখন আছে ১ তাহলে হয়ে যাবে ০ , যদি থাকে ০ তাহলে হয়ে যাবে ১ ) 
2. যদি আমরা ফ্লিপ করি তাহলে তার চাইল্ডের চাইল্ড মানে , আমরা এখন যদি থাকি   লেভেল ২ এর কোন নোডে । তাহলে লেভেল ৪ , ৬ , ৮ ......।। নোডের ভ্যালুও ফ্লিপ হবে ।   

আমাকে বলতে হবে আমি মিনিমাম কতটা ফ্লিপ অপারেশন এর মাধ্যমে এখন যেই অবস্থাতে আছি তা থেকে আমি আমার target stage এ  পৌঁছাতে পারব ।
আমরা কিছু সিন্ধান্ত নিতে পারি যেহেতু এইটা একটা ট্রি তাই । 

1.  এইখানে রুট বলা হইছে নোড ১কে ।  রুট থেকে আমি DFS চালাব । 
2. যখনই আমি দেখব আমার কারেন্ট যে ভ্যালু আছে তা আমার টার্গেট ভ্যালু এর সাথে ম্যাচ করছে না তখনই আমি ফ্লিপ করে দিব । যদিও এইটা দেখার আগে আমাকে দেখে নিতে হবে আমার কারেন্ট যে ভ্যালু আছে তার কোন দাদা বা দাদার দাদা এর থেকে তার ভ্যালু এখন ফ্লিপ হচ্ছে কিনা । 
3. কারেন্ট যে ভ্যালু আছে তা ফ্লিপ করতে হবে কি হবে না এইটা বুঝার জন্য আমাকে একটা ভ্যারিএবল রাখতে হবে । 
4. DFS call হবে এইরকম ভাবে DFS( current_node , parent , need_to_flip_now , need_to_flip_my_child )

কোড 

	const int NX = 1e5 + 10 ; // limit of the graph
	vector < int > g[NX] , ans ;
	int given[NX] , target[NX] ;
	void dfs( int curren_node , int parent , int need_to_flip_now , int need_to_flip_my_child )
	{
	if( need_to_flip_now ) given[current_node] ^= 0 ;
	if( given[current_node] != target[current_node] )
	{
	ans.push_back( current_node ); // we need to flip that node ;
	need_to_flip_now ^= 0 ;
	}
	for ( int u = 0 ; u < g[current_node].size() ; u++ )
	{
	if( g[current_node][u] != parent ) dfs( g[current_node][u] , current_node , need_to_flip_my_child , need_to_flip_now);
	// look here we swap the variable need_to_flip_now to need_to_flip_my_child
	// as what is need_to_flip_my_child is the next level need_to_flip_now
	}
	}

view raw one.cpp hosted with ❤ by GitHub

রান টাইম হবে O(node)
Distance in Tree :
এইটা অনেক চমৎকার একটা প্রবলেম । আমাদের একটা ট্রি দেওয়া হবে , আর একটা ভ্যালু K দেওয়া থাকবে , আমাদের বলতে হবে আমরা ট্রিতে কতটা distinct pair of nodes পাব যাদের মধ্যে distance হবে আমার K ।
প্রবলেমটা পড়ে একটু কঠিন মনে হইল এর সমাধান অনেক ইজি । tree dp এর প্রবলেম ও বলে এই ধরনের প্রবলেমকে ।
কিভাবে করর :

1. যেহেতু এইটা রুটেট ট্রি , কোন রুট u হলে , এর দুইটা চাইল্ড v আর w হইলে , তাদের মধ্যে distance হচ্ছে , v - u প্লাস u - w .
2. আমরা খুব সহজেই তাহলে কোন রুট এর দুইটা সাব ট্রি থেকে এর চাইল্ডের মধ্যে k distance এর রিলেশন পেতে পারি । রিলেশনটা হবে
    
          Ans += (  j = 1 to k ) dp[u][j-1] * dp[v][ k - j ]   ;
   এইখানে ,
        ( j - 1 + k - j + distance( u , v )  == k )
3. এখন প্রতিটা সাব ট্রি এর ক্যালকুলেশন এর পর আমার ট্রি এর নোড এর লেভেল আপডেট করব ।   

             ( j = 1 to k ) dp[u][j] += dp[v][j-1] ;

কোড :

	const int NX = 50000 + 10 ;
	const int MX = 500 + 10 ;
	vector < int > adj[NX];
	int deg[NX];
	int dp[NX][MX] ;
	Long ans ;
	int n , k ;
	void dfs( int x , int par )
	{
	dp[x][0] = 1 ;
	rep( i , deg[x] )
	{
	int u = adj[x][i];
	if( u == par ) continue ;
	dfs( u , x );
	for ( int j = 1 ; j <= k ; j++ ) ans += (Long) ( dp[x][j-1] * dp[u][k-j]); // লেফট এবং রাইট সাব ট্রি এর মধ্যে রিলেশন থেকে আন্সার এড করছি
	for ( int j = 1 ; j <= k ; j++ ) dp[x][j] += dp[u][j-1] ; // রুট থেকে কত দুরুত্বে কয়েকটা নোড আছে আপডেট করছি
	// আমাদের শুধুমাত্র k distance এর নোড গুলা বিবেচনা করতে হবে ।
	}
	}

view raw dfs2.cpp hosted with ❤ by GitHub

এই কোডের রান টাইম হবে O( Node * K ) .

Find Lexicographically Smallest Permutation :
আমাদের এই প্রবলেম এ বলা হইছে আমাদের একটা N সাইজের Array দেওয়া থাকবে । এই array থেকে lexicographically smallest permutation আমাদের প্রিন্ট দিতে হবে কিন্তু এইখানে একটা রেস্ট্রিকশন দেওয়া আছে আমরা চাইলেই যেকোন পজিশন এর ভ্যালু swap করতে পারি না । আমাদের কিছু good position দেওয়া আছে আমরা শুধু মাত্র সেই পজিশন এর মধ্যে ভ্যালু swap করতে পারি ।

Observation 1 :

এইখানে যদি আমরা লক্ষ্য করি complete connected position গুলাতে Array তে যাই ভ্যালু থাকুক না কেন আমরা এই পজিশন গুলার মধ্যে যেহেতু swap করতে পারি ফাইনাল array তে অবশ্যই এই পজিশনগুলার মধ্যে sorted value থাকবে ।

Observation 2:
আমরা যদি এখন observation 1 এর আইডিয়া থেকে array এর উপর dfs চালাই তাহলে আমরা complete connected position গুলার সাথে সাথে আমরা ফাইনাল array তে কি থাকবে তাও পেয়ে যাব ।

	const int NX = 1e3 + 10 ;
	vector < int > comp , tmp ;
	vector < int > adj[NX];
	bool vis[NX];
	int n , m , inp[NX] ;
	void clean()
	{
	rep( i , n + 4 )
	{
	vis[i] = 0 ;
	adj[i].clear();
	}
	}
	void dfs( int x )
	{
	int sz = adj[x].size();
	vis[x] = 1 ;
	comp.pb(x);
	tmp.pb(inp[x]);
	rep( i , sz )
	{
	int u = adj[x][i];
	if( vis[u] ) continue ;
	dfs(u);
	}
	}
	int main()
	{
	// I will always use scanf and printf
	// May be i won't be a good programmer but i will be a good human being
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , m = II ;
	clean();
	rep( i , n ) inp[i] = II ;
	rep( i , m )
	{
	int x = II , y = II ;
	x-- , y-- ;
	adj[x].pb(y);
	adj[y].pb(x);
	}
	rep( i , n )
	{
	if( vis[i] == 0 )
	{
	dfs(i);
	sort(comp.begin() , comp.end());
	sort(tmp.begin() , tmp.end());
	int sz = comp.size();
	rep( j , sz )
	{
	inp[comp[j]] = tmp[j];
	}
	comp.clear();
	tmp.clear();
	}
	}
	for( int i = 0 ; i < n - 1 ; i++ ) printf("%d ",inp[i]);
	printf("%d\n",inp[n-1]);
	}
	return 0;
	}

view raw dfs3.cpp hosted with ❤ by GitHub

এই কোডের রান টাইম কি হবে ? এইটা পাঠকদের উদ্দেশ্যই রেখে দিলাম :D

ইচ্ছা আছে এই সিরিজটা আরো বড় করার । ধন্যবাদ পড়ার জন্য ।