Beautiful Graph Problems

-

Cycle in a 2D graph with DFS

Problem Link : Fox And Two Dots

Solution Idea : This problem can be solved using DFS. You can Check my Solution .

Coloring a graph 

Problem Link : Coloring a Tree

Solution Idea : Using DFS we can color a node and its subtree. We are coloring only subtrees. so we can't visit upwards of a tree while coloring. That's why we are using directed graph. if a tree is already colored in it's required color, we don't need to color it anymore. You can Check my Solution.

Also solved Customized Chess Board ( brute force approach )

Location: Bangladesh
Currently, I am completing my Bachelor of Science ( Engineering ) degree in computer science and engineering. I am a Programming Competition and problem solving Enthusiast. Competed in 12+ Programming Competition both national and regional. I prefer to code in C, C++ and Python. Problems related to Dynamic programming and Graph algorithms are my favourites to solve. I've solved and tried more than 1500+ programming problems in different online judges like UVa online judge, Lightoj, Sphere online judge, Codeshef, Timus online judge, Hackerrank, HUST virtual judge and Codeforces.

Comments

Post a Comment

Popular posts from this blog

Appleman and Tree - CF 461B

-
Image
  প্রবলেমটা  মূলত ডিপি অন ট্রি প্রবলেম। এখানে একটা ট্রি দেয়া আছে , যার প্রত্যেকটা নোড হয় ব্লাক অথবা হোয়াইট। এখন লক্ষ্য করি, ট্রির যেকোনো একটি এজ যদি আমরা ডিলিট করি তাহলে দুইটি নতুন ট্রি পাবো । দুটি এজ ডিলিট করলে আমরা তিনটি নতুন ট্রি পাবো। অর্থাৎ , ক সংখ্যক এজ ডিলিট করলে আমরা ক+১ টি নতুন ট্রি/ কম্পোনেন্ট পাবো। কিন্তু আমাদের এমন ভাবে এজগুলো ডিলিট করতে হবে যাতে  ডিলিট করার পর প্রত্যেকটা কম্পোনেন্ট এ একটি মাত্র ব্লাক নোড থাকে। বলতে হবে এমন কত উপায়ে ট্রি এর এজগুলোকে ডিলিট করা যাবে। কিছু বিষয় লক্ষ্য করা যাক। যদি ট্রি তে সবগুলো নোড ই ব্লাক হয় তাহলে এক উপায়েই  তাদের এজগুলো ডিলিট করা যায় । যদি ট্রি এর রুট নোড ব্লাক হয় এবং চাইল্ড নোড হোয়াইট হয়,  তাহলে তার চাইল্ড নোডের সাথে থাকা এজটিকে আমরা ডিলিট করতেও পারি নাও করতে পারি। রুট নোড হোয়াইট আর চাইল্ড নোড ব্লাক হলেও একই বিষয়। হোয়াইট নোড এর চাইল্ড হোয়াইট নোড হলেও তাই ।  সুতরাং , আমাদের যদি জানা থাকে চাইল্ড নোড গুলোর প্রত্যেক্টার জন্য কত উপায়ে এজ স্প্লিট করা যায় আমরা রুট নোডের জন্যও কম্বিনেশন বের করে ফেলতে পারি। এখানে , খেয়া...
Read more

Lightoj 1236 - Pairs Forming LCM

-
The  problem  statement actually refers to finding out number of pairs of integers that have LCM n ( which is the given value). There can be 2000 test cases and value of n can be at most 10 14 . let's assume that the prime factorization of n can be represented as n = p1 q1 .p2 q2 .......px qx , where p1,p2....px are prime numbers and q1,q2...qx are corresponding powers. lets assume that any two integers are i and j such that LCM(i,j)=n. since n is their LCM, the prime factorization of i and j must have the following qualities. 1. if i = px qx then j must be either j = px qx-1 or j = px qx-2 or ..... j = px 0 2. if j = px qx then i must be either i = px qx-1 or i = px qx-2 or ..... i = px 0 3. i = px qx and j = px qx for the 1st scenario we can see there are qx combinations for the 2nd scenario we can see there are qx combinations for the 3rd scenario we can see there are 1 combinations so, there can be a total of 2*qx + 1 combinations for each of the pr...
Read more

A Simple Kruskal Algorithm

-
Image
#include<bits/stdc++.h> ///...................................*****................................................./// /// Author : Raihan Khan Raka ( raihankhanraka@gmail.com ) /// /// Department of Computer Science /// /// & Engineering /// /// Comilla University , Bangladesh. /// ///...................................*****................................................./// /*....................................Values................................................*/ #define p5 100007 #define p6 1000007 #define PI acos(-1) #define M 1000000007 #define inf 1LL << 62 #define white 0 #define gr...
Read more