Hey Codechef can u please tell me the way to solve this question http://codeforces.com/contest/893/problem/C without using the BFS DFS search and SIMILARITY PROPERTY as provided in their contest tutorials … I just want to solve it using iterative way can anyone plzz tell me the way how to store all the nodes (characters in the above ques) in just one location (by using vector of vectors) and then iterate over it for each corresponding vector[i] representing the path starting from the i th node ANY HELP WILL BE APPRECIATED !!!
You can create an adjacency list storing all edges vertex-wise.
Make a visited boolean array, keeping record of visited vertices.
Also, initialise ans variable to 0.
Now, loop for all vertices, and for every unvisited vertices, create a stack(queue for bfs), add current vertex and run dfs, and find minimum value of all values associated to all vertices connected to current vertex.(initialise min value to 1e15)
Just add this min value to ans for every unvisited vertex.
Print ans. 
1 Like
Here’s my solution(iterative). See it only after a try. 
Click to view
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
static final long MOD = (long)1e9+7;
static FastReader in; static int MAX = (int)1e6;
static ArrayList[] adj;
public static void main(String[] args){
in = new FastReader();
int N = ni(), M = ni();
long[] A = new long[N+1];
for(int i = 1; i<=N; i++)A[i] = nl();
adj = new ArrayList[N+1];
for(int i = 1; i<=N; i++)adj[i] = new ArrayList<>();
for(int i = 0; i< M; i++){
int u = ni(), v = ni();
adj[u].add(v); adj[v].add(u);
}
boolean[] visited = new boolean[N+1];
Stack s = new Stack<>();
long ans = 0; for(int i = 1; i<=N; i++){
if(!visited[i]){
s.push(i);
visited[i] = true;
long cost = A[i];
while(!s.isEmpty()){
int x = s.pop();
for(int j:adj[x]){
if(!visited[j]){
visited[j] = true;
s.push(j);
cost = Math.min(cost, A[j]);
}
}
}
ans += cost;
}
}
pn(ans);
}
}
PS: i have removed my IO template due to its bulky size. ni() inputs an integer and pn() works same way as System.out.println().
Thnakyou so much for ur time and this nice explanation i,ll definitely solve it without using the solution
That’s alright…
Friend, dont go on awarding 21 points like this… Accepting answer would be enough…
Just drop a new answer below, so that i could return ur points.