Weighted Quick Union Find Algorithm

public class WeightedQuickUnionUF {
 private int[] id;
 private int[] size;

 public WeightedQuickUnionUF(int N) {
  id = new int[N];
  size =  new int[N];
  for (int i = 0; i < N; i++) {
   id[i] = i;
   size[i] = 0;
  }
 }

 private int root(int i) {
  while (i != id[i])
   i = id[i];
  return i;
 }

 //log(N)
 public boolean connected(int p, int q) {
  return root(p) == root(q);
 }
 //log(N)
 public void union(int p, int q) {
  int i = root(p);
  int j = root(q);
  if (i == j)
   return;
  if (size[i] < size[j]) {
   id[i] = j;
   size[j] += size[i];
  } else {
   id[j] = i;
   size[i] += size[j];
  }
 }
}

public class Main {

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int N = in.nextInt();  
  WeightedQuickUnionUF wQuickUnionUF = new WeightedQuickUnionUF(N);
  while (in.hasNext()) {
   int p = in.nextInt();
   int q = in.nextInt();
   if (!wQuickUnionUF.connected(p, q)) {
    wQuickUnionUF.union(p, q);
   } else
    System.out.println("Already Connected");
  }
 }

}

Dijkstra Algorithm

 
#include
#include
#define inf 1000000000
#define SIZE1 20000
#define SIZE2 50000
using namespace std;
typedef vectorgraph;
long Q[SIZE1+9],d[SIZE1+9],positionOf[SIZE1+9];
graph G[SIZE2*2+9],W[SIZE2*2+9];
//posiotionOf[]= posiontion of one node in Q[] or tree
//Q[] is a tree or collection of nodes in priority sequences.
//d[]= the minimum values to reach in nodes. 

int min_heapify(long i,long n){
	long temp,minimum,l,r;
	l=2*i;
	r=2*i+1;
	if(l<=n && d[Q[l]]d[Q[i]]){
			temp=Q[i/2];
			Q[i/2]=Q[i];
			Q[i]=temp;		
			positionOf[Q[i]]=i;
			positionOf[Q[i/2]]=i/2;		
			i=i/2;
		}
		else
			break;		
	}
	return 0;
}
int main(){
	long i,j,n,m,u,v,w,source,dest,t;	
	scanf("%ld",&t);
	for(j=1;j<=t;j++){		
		scanf("%ld%ld%ld%ld",&n,&m,&source,&dest);
		for(i=1;i<=n;i++){
			G[i].clear();
			W[i].clear();
			d[i]=inf;
			Q[i]=i;
			positionOf[i]=i;
		}
		for(i=1;i<=m;i++){
			scanf("%ld%ld%ld",&u,&v,&w);
			G[u+1].push_back(v+1);
			G[v+1].push_back(u+1);
			W[u+1].push_back(w);
			W[v+1].push_back(w);
		}		
		d[source+1]=0;update_min_heap(source+1);
		while(n>0)
		{
			u=extract_min_Q(n);
			n--;
			for(v=0;v1)
					{
						update_min_heap(positionOf[G[u][v]]);
					}

				}
			}			
		}		
		if(d[dest+1]==inf)
			printf("Case #%ld: unreachable\n",j);
		else
			printf("Case #%ld: %ld\n",j,d[dest+1]);
	}
	return 0;
}

About This Blog

This Blog is only for myself.

প্রজাপতির অস্বাভাবিক পরিবর্তন

জাপানে তেজস্ক্রিয় পদার্থের মিশ্রণের প্রভাব পড়েছে পরিবেশের ওপর। দেশটিতে বিকারগ্রস্ত প্রজাপতির অস্তিত্ব পাওয়া গেছে। ফুকুশিমা পারমাণবিক দুর্ঘটনার পর সংগৃহীত প্রজাপতি গবেষণা করে এর প্রমাণ মিলেছে।

গবেষণায় দেখা গেছে, প্রজাপতির অস্বাভাবিক পরিবর্তন। বৃদ্ধি পেয়েছে বিকারগ্রস্ত পা, শুঙ্গ ও পাখার সংখ্যা। আর বিকারগ্রস্ত এসব প্রজাপতির সঙ্গে তেজস্ক্রিয় পদার্থের সম্পর্ক রয়েছে। গবেষণার ফল সায়েন্টিফিক রিপোর্টস সাময়িকীতে প্রকাশ করা হয়েছে।২০১১ সালের মার্চে ভয়াবহ সুনামির জেরে ফুকুশিমা পরমাণু বিদ্যুৎ প্রকল্পে বিপর্যয়ের পরপরই ওই এলাকায় শুককীট (প্রজাপতির জীবন চক্রের প্রথম পর্যায়) অবস্থায় শতকরা ১২ ভাগ প্রজাপতির মধ্যে অস্বাভাবিক পরিবর্তন লক্ষ্য করা গেছে। ঘটনার দুই মাস পর জাপানি গবেষকেরা ফুকুশিমাসহ ১০টি স্থান থেকে একটি নির্দিষ্ট প্রজাপতির ১৪৪টি প্রাপ্তবয়স্ক প্রজাপতি সংগ্রহ করেন। দুর্ঘটনার সময় জীবনচক্রের প্রথম ধাপে ছিল সাধারণত এমন প্রজাপতিই সংগ্রহ করা হয়। গবেষণায় দেখা যায়, তেজস্ক্রিয় পদার্থের প্রভাব বেশি পড়েছে—এমন এলাকার প্রজাপতির পাখা তুলনামূলক অনেক ছোট এবং এর চোখের বৃদ্ধিও ঘটেছে অসমভাবে।দুর্ঘটনার ছয় মাস পর আবার ওই ১০টি স্থান থেকে প্রজাপতি সংগ্রহ করা হয়। এগুলো গবেষণা করে দেখা যায়, ফুকুশিমা থেকে সংগৃহীত প্রজাপতির বিকারের মাত্রা দুর্ঘটনার দুই মাস পর সংগ্রহ করা প্রজাপতির বিকারের চেয়ে দ্বিগুণেরও বেশি। গবেষক দলের প্রধান ওকিনাওয়ার ইউনিভার্সিটি অব রিউকিউসের অধ্যাপক জজি ওতাকি বলেন, ‘এটা সব সময়ই ধরে নেওয়া হতো যে, কীটপতঙ্গ হচ্ছে তেজস্ক্রিয় প্রতিরোধকারী। ওই ধারণা অনুযায়ী, আমাদের গবেষণার ফল হয়েছে অপ্রত্যাশিত।’গবেষকেরা বলেন, দূষিত খাদ্যের ফলে প্রজাপতির বিকার হয়েছে। অথচ এসব প্রজাপতির পূর্ববর্তী প্রজন্মে এ ধরনের কোনো বিকার ছিল না।গবেষক দলটি ১০ বছরেরও বেশি সময় ধরে এই নির্দিষ্ট প্রজাতির প্রজাপতি নিয়ে গবেষণা করছেন। পরিবেশগত পরিবর্তন এই প্রজাতির ওপর ব্যাপকভাবে প্রভাব ফেলে। নতুন গবেষণার মাধ্যমে এটাই প্রতীয়মান হয়েছে, প্রাণীকূলের ওপর ফুকুশিমা দুর্ঘটনার প্রভাব এখনো পড়ছে। তেজস্ক্রিয়তার মাত্রা কমে এলেও প্রাণীকূল প্রভাবিত হচ্ছে। বিবিসি।

মঙ্গলে নামল কিউরিওসিটি

অবশেষে সব উৎকণ্ঠার অবসান ঘটিয়ে মঙ্গলে নামল নাসার রোবট যান রোভার কিউরিওসিটি। গতকাল সোমবার গ্রিনিচ মান সময় ভোর পাঁচটা ৩২ মিনিটে (বাংলাদেশ সময় বেলা সাড়ে ১১টা) লাল গ্রহটিতে সফলভাবে অবতরণ করে মাকড়সা আকৃতির এ যানটি।  

মঙ্গল গবেষণার ইতিহাসে এটিই এখন পর্যন্ত নাসার বিজ্ঞানীদের সবচেয়ে বড় সাফল্য। রোবট যানটির ওজন প্রায় এক টন। এই প্রথম নাসা এত বেশি ওজনের যান কোনো গ্রহে সফলভাবে নামাতে সক্ষম হলো। 

কিউরিওসিটির মঙ্গলে অবতরণ নিয়ে উৎকণ্ঠ ছিল নাসার বিজ্ঞানীদের মধ্যে। তাই কিউরিওসিটির অবতরণের ঘোষণার পর মার্কিন মহাকাশ গবেষণা সংস্থার (নাসা) জেট প্রপালশন ল্যাবরেটরির বিজ্ঞানীরা উল্লাসে ফেটে পড়েন। প্রধান বিজ্ঞানীরা ‘মার্স চকোলেট’ বার নাসার কর্মীদের মধ্যে বিতরণ করেন। 

নাসার প্রশাসক চার্লস বোল্ডেন বলেন, ‘আমরা আবারও মঙ্গলে—এটা সত্যিই অবিশ্বাস্য! এর চেয়ে ভালো কিছু হতে পারে না। 

কিউরিওসিটির পাঠানো প্রথম ছবিটি ধূসর। তাতে রোভারের চাকা মঙ্গলের মাটি স্পর্শ করার দৃশ্য দেখা গেছে। কয়েক সেকেন্ডের ব্যবধানে দ্বিতীয় ছবি পাঠায় রোভার, তাতে রয়েছে মঙ্গলে রোভারের ছায়া। 

মঙ্গলের আবহাওয়া মন্ডলে প্রবেশের আগ মুহূর্তে মহাকাশ যানটির গতি ছিল ঘণ্টায় ১৩ হাজার ২০০ মাইল। প্রথমে সুপারসনিক প্যারাসুটের সাহায্যে গতি কমানো হয়। পরে গতি আরো নিয়ন্ত্রণে আনা হয়। এরপর ক্রেনের মাধ্যমে ধীরে ধীরে ছয় চাকায় ভর করে ভূমিতে নামে রোভার। এ সময় এটির গতি ছিল সেকেন্ডে মাত্র শূন্য দশমিক ৬ মিটার। অবতরণের জন্য আগেই গিরিখাদ গেইল কার্টার বেছে নেওয়া হয়েছিল। এখানে অতীতে পানি থাকার অনেক চিহ্ন পাওয়া গেছে। আগামী দুই বছর কিউরিওসিটি গিরিখাদের তলা থেকে ধীরে ধীরে ওপরে উঠবে। এটি পাথুরে ভূমি খুঁড়ে দেখবে, সেখানে প্রাণের বিকাশের কোনো পরিবেশ আছে কি না। 

মঙ্গলে অবস্থানকালে পারমাণবিক শক্তিতে চলবে কিউরিওসিটি। এটি নানা বৈজ্ঞানিক যন্ত্রপাতিতে ঠাসা। আছে ক্যামেরা, আবহাওয়া নিরীক্ষণ কেন্দ্র, শক্তিশালী ড্রিলসহ রোবটিক হাত, দূর থেকে পাথর চূর্ণ-বিচূর্ণ করতে সক্ষম লেজার, রাসায়নিক গবেষণাগার ও বিকিরণ মাপার যন্ত্র। 

কিউরিওসিটি মঙ্গলে মানুষ কিংবা জীবের অস্তিত্ব খুঁজে পাবে—এমনটা প্রত্যাশা করছেন না বিজ্ঞানীরা। তবে তাঁরা আশা করছেন, এটির সাহায্যে মঙ্গলের মাটি ও পাথর গবেষণা করে তাঁরা জানতে পারবেন, সেখানে অতীতে প্রাণীর অস্তিত্ব ছিল কি না। এ ছাড়া ভবিষ্যতে মানুষের যাওয়ার উপযোগী পরিবেশ আছে কি না, তা-ও গবেষণা করে দেখা হবে। 

২০১১ সালের নভেম্বর মাসে ফ্লোরিডার কেপ ক্যানাভারেল থেকে যাত্রা শুরু করে কিউরিওসিটি। সাড়ে আট মাসের এই অভিযানে যানটি এরই মধ্যে বিকিরণের ওপর নানা তথ্য সংগ্রহ করেছে। মঙ্গলের পথে কিউরিওসিটি ৩৫ কোটি ২০ লাখ মাইল পাড়ি দিয়েছে। ১২ বছরের প্রস্তুতি শেষে এ প্রকল্পে ব্যয় হয়েছে ২৫০ কোটি ডলার। 

১৯৬০ সাল থেকে সারা বিশ্বের মহাকাশ গবেষণা সংস্থাগুলোর মঙ্গল গ্রহে বেশির ভাগ অভিযানই ব্যর্থ হয়েছে। সফলতার হার প্রায় ৪০ শতাংশ। অধিকাংশ ক্ষেত্রেই ধূলিঝড় বা যান্ত্রিক ত্রুটির মতো প্রতিকূলতায় পড়তে হয়েছে বিজ্ঞানীদের। 

বিবিসি ও এএফপি।