8000 Add files via upload · shivamkumar177/LeetcodeMay@4bc76ea · GitHub
[go: up one dir, main page]
Skip to content

Commit 4bc76ea

Browse files
aman2382000aman2382000
authored
Add files via upload
1 parent 9036e00 commit 4bc76ea

File tree

1 file changed

+209
-0
lines changed

1 file changed

+209
-0
lines changed

‎bfs.java

Lines changed: 209 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,209 @@
1+
/*
2+
A 10000 man Agarwal
3+
algo.java
4+
*/
5+
6+
import java.util.*;
7+
import java.io.*;
8+
9+
public class bfs
10+
{
11+
static class FastReader
12+
{
13+
BufferedReader br;
14+
StringTokenizer st;
15+
16+
public FastReader()
17+
{
18+
br = new BufferedReader(new InputStreamReader(System.in));
19+
}
20+
21+
String next()
22+
{
23+
while (st == null || !st.hasMoreElements())
24+
{
25+
try
26+
{
27+
st = new StringTokenizer(br.readLine());
28+
}
29+
catch (IOException e)
30+
{
31+
e.printStackTrace();
32+
}
33+
}
34+
return st.nextToken();
35+
}
36+
37+
int nextInt()
38+
{
39+
return Integer.parseInt(next());
40+
}
41+
42+
long nextLong()
43+
{
44+
return Long.parseLong(next());
45+
}
46+
47+
double nextDouble()
48+
{
49+
return Double.parseDouble(next());
50+
}
51+
52+
String nextLine()
53+
{
54+
String str = "";
55+
try
56+
{
57+
str = br.readLine();
58+
}
59+
catch (IOException e)
60+
{
61+
e.printStackTrace();
62+
}
63+
return str;
64+
}
65+
}
66+
67+
68+
static FastReader sc = new FastReader();
69+
static PrintWriter out = new PrintWriter(System.out);
70+
static int ni()throws IOException{return sc.nextInt();}
71+
static long nl()throws IOException{return sc.nextLong();}
72+
static int[][] nai2(int n,int m)throws IOException{int a[][] = new int[n][m];for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j] = ni();return a;}
73+
static int[] nai(int N,int start)throws IOException{int[]A=new int[N+start];for(int i=start;i!=(N+start);i++){A[i]=ni();}return A;}
74+
static Integer[] naI(int N,int start)throws IOException{Integer[]A=new Integer[N+start];for(int i=start;i!=(N+start);i++){A[i]=ni();}return A;}
75+
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
76+
static char[] nac()throws IOException{char[]A=sc.next().toCharArray();return A;}
77+
static void print(int arr[]){for(int i=0;i<arr.length;i++)out.print(arr[i]+" ");out.println();}
78+
static void print(long arr[]){for(int i=0;i<arr.length;i++)out.print(arr[i]+" ");out.println();}
79+
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
80+
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
81+
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));} // return the number of set bits.
82+
static boolean isPrime(int number){if(number==1) return false;if (number == 2 || number == 3){return true;}if (number % 2 == 0) {return false;}int sqrt = (int) Math.sqrt(number) + 1;for(int i = 3; i < sqrt; i += 2){if (number % i == 0){return false;}}return true;}
83+
static boolean isPrime(long number){if(number==1) return false;if (number == 2 || number == 3){return true;}if (number % 2 == 0) {return false;}long sqrt = (long) Math.sqrt(number) + 1;for(int i = 3; i < sqrt; i += 2){if (number % i == 0){return false;}}return true;}
84+
static int power(int n,int p){if(p==0)return 1;int a = power(n,p/2);a = a*a;int b = p & 1;if(b!=0){a = n*a;}return a;}
85+
static long power(long n,long p){if(p==0)return 1;long a = power(n,p/2);a = a*a;long b = p & 1;if(b!=0){a = n*a;}return a;}
86+
static void reverse(int[] a) {int b;for (int i = 0, j = a.length - 1; i < j; i++, j--) {b = a[i];a[i] = a[j];a[j] = b;}}
87+
static void reverse(long[] a) {long b;for (int i = 0, j = a.length - 1; i < j; i++, j--) {b = a[i];a[i] = a[j];a[j] = b;}}
88+
static void swap(int a[],int i,int j){a[i] = a[i] ^ a[j];a[j] = a[j] ^ a[i];a[i] = a[i] ^ a[j];}
89+
static void swap(long a[],int i,int j){a[i] = a[i] ^ a[j];a[j] = a[j] ^ a[i];a[i] = a[i] ^ a[j];}
90+
static int count(int n){int c=0;while(n>0){c++;n = n/10;}return c;}
91+
static int[] prefix_sum(int a[],int n){int s[] = new int[n];s[0] = a[0];for(int i=1;i<n;i++){s[i] = a[i]+s[i-1];}return s;}
92+
static long[] prefix_sum_int(int a[],int n){long s[] = new long[n];s[0] = (long)a[0];for(int i=1;i<n;i++){s[i] = ((long)a[i])+s[i-1];}return s;}
93+
static long[] prefix_sum_Integer(Integer a[],int n){long s[] = new long[n];s[0] = (long)a[0];for(int i=1;i<n;i++){s[i] = ((long)a[i])+s[i-1];}return s;}
94+
static long[] prefix_sum_long(long a[],int n){long s[] = new long[n];s[0] = a[0];for(int i=1;i<n;i++){s[i] = a[i]+s[i-1];}return s;}
95+
static boolean isPerfectSquare(double x){double sr = Math.sqrt(x);return ((sr - Math.floor(sr)) == 0);}
96+
static ArrayList<Integer> sieve(int n) {int k=0; boolean prime[] = new boolean[n+1];ArrayList<Integer> p_arr = new ArrayList<>();for(int i=0;i<n;i++) prime[i] = true;for(int p = 2; p*p <=n; p++){ k=p;if(prime[p] == true) { p_arr.add(p);for(int i = p*2; i <= n; i += p) prime[i] = false; } }for(int i = k+1;i<=n;i++){if(prime[i]==true)p_arr.add(i);}return p_arr;}
97+
static boolean[] seive_check(int n) {boolean prime[] = new boolean[n+1];for(int i=0;i<n;i++) prime[i] = true;for(int p = 2; p*p <=n; p++){ if(prime[p] == true) { for(int i = p*2; i <= n; i += p) prime[i] = false; } }prime[1]=false;return prime;}
98+
static int get_bits(int n){int p=0;while(n>0){p++;n = n>>1;}return p;}
99+
static int get_bits(long n){int p=0;while(n>0){p++;n = n>>1;}return p;}
100+
static int get_2_power(int n){if((n & (n-1))==0)return get_bits(n)-1;return -1;}
101+
static int get_2_power(long n){if((n & (n-1))==0)return get_bits(n)-1;return -1;}
102+
//gives the divisors of first n natural numbers in n*sqrt(n) time..
103+
static ArrayList<ArrayList<Integer>> divisors_n(int n){int i,j;ArrayList<ArrayList<Integer>> ans = new ArrayList<>();ArrayList<Integer> arr = new ArrayList<>();arr.add(1);ans.add(arr);for (i = 2; i <= n; i++){arr = new ArrayList<>();for (j = 1; j * j <= i; j++){if (i % j == 0){arr.add(j);if (i / j != j)arr.add(i/j);}}ans.add(arr);} return ans;}
104+
//gives divisors of a particular number in sqrt(n) time..
105+
static ArrayList<Integer> divisors_1(int n){ArrayList<Integer> ans = new ArrayList<>();for (int i=1; i<=Math.sqrt(n); i++){if (n%i==0){if (n/i == i)ans.add(i);else{ans.add(i);ans.add(n/i);}}}return ans;}
106+
static void close(){out.flush();}
107+
108+
/*-------------------------Main Code Starts(algo.java)----------------------------------*/
109+
110+
static Map<Integer,List<Integer>> graph;
111+
static List<Integer> vert;
112+
static Map<Integer,Boolean> visited;
113+
static List<Integer> bfs_traversal;
114+
115+
static void printgraph(int v) throws IOException
116+
{
117+
System.out.println();
118+
System.out.println("*****************");
119+
for(int i=0;i<v;i++)
120+
{
121+
int x = vert.get(i);
122+
System.out.println(x+" ---> "+graph.get(x));
123+
}
124+
System.out.println("******************");
125+
}
126+
127+
static void createGraph(int e,int v,boolean directed) throws IOException
128+
{
129+
System.out.println("Enter all the vertices -> ");
130+
for(int i=0;i<v;i++)
131+
{
132+
int x = ni();
133+
vert.add(x);
134+
graph.put(x,new ArrayList<Integer>());
135+
}
136+
137+
System.out.println("Enter all the edges -> ");
138+
for(int i=0;i<e;i++)
139+
{
140+
System.out.print("Source : ");
141+
int src = ni();
142+
System.out.print("Dest : ");
143+
int dest = ni();
144+
145+
List<Integer> arr = graph.get(src);
146+
arr.add(dest);
147+
graph.put(src,arr);
148+
if(!directed)
149+
{
150+
arr = graph.get(dest);
151+
arr.add(src);
152+
graph.put(dest,arr);
153+
}
154+
}
155+
}
156+
157+
158+
static void bfs(int src)
159+
{
160+
Queue<Integer> q = new LinkedList<>();
161+
q.add(src);
162+
visited.put(src,true);
163+
while(q.size()>0)
164+
{
165+
int x = q.poll();
166+
bfs_traversal.add(x);
167+
for(Integer neighbours : graph.get(x))
168+
{
169+
if(!visited.containsKey(neighbours))
170+
{
171+
q.add(neighbours);
172+
visited.put(neighbours,true);
173+
}
174+
}
175+
}
176+
}
177+
178+
public static void solve() throws IOException
179+
{
180+
181+
int n_edges = ni();
182+
int n_vert = ni();
183+
184+
createGraph(n_edges,n_vert,true);
185+
printgraph(n_vert);
186+
187+
for(int i=0;i<n_vert;i++)
188+
{
189+
if(!visited.containsKey(vert.get(i)))
190+
bfs(vert.get(i));
191+
}
192+
System.out.println("BFS traversal is : "+bfs_traversal);
193+
}
194+
195+
public static void main(String[] args) throws IOException
196+
{
197+
int test = 1;
198+
//test = sc.nextInt();
199+
graph = new HashMap<>();
200+
vert = new ArrayList<Integer>();
201+
visited = new HashMap<>();
202+
bfs_traversal = new ArrayList<>();
203+
while(test-- > 0)
204+
{
205+
solve();
206+
}
207+
close();
208+
}
209+
}

0 commit comments

Comments
 (0)
0