Problem Link-TRATCK1 Problem - CodeChef
Please explain your approach for this problem.
Please tell me how to deal with problems as i am new to graph theory?
Problem Link-TRATCK1 Problem - CodeChef
Please explain your approach for this problem.
Please tell me how to deal with problems as i am new to graph theory?
Question is simple you need to find total number of connected components.
Connected Component says that in a graph every other node is reachable by any other node following any path in the connected graph.
Just calculate the number of connected components
Suppose there are X connected components.
In the test case mentioned, there are THREE CONNECTED COMPONENTS. Simply, to connect them you’d need X - 1 number of Paths to make each node reachable by other in the entire given graph.
For this you’d need a DFS Approach and start like this
count = 0; for(int i = 0;i < N; i++) // where i represents a node { if(!visited[i]) { { DFS(i) // where i is source for present DFS logic count += 1; } }
Count finally gives you number of connected components, Your answer = count - 1 in every case.
Use this link for Connected Components for more information.
Connected Components
I thought I should post in this new thread.
I am actually printing com-1, so when n==0 then com=1 and com-1 will be printed which will be zero.
So there is some other bug for that WA verdict.
For your second query
Think of map as an array.
map < type1, type2>mapname;
type1 is the index of that array and type2 is the kind of data stored in that array. So if you write vector in place of type2 then a vector can be stored in an array.
Example of map as an array : map < int,int > ar
ar can be used as a normal array. Also the default value in ar is zero.
why we all are getting Wrong Answers?
I think the tester’s solution is wrong, that’s why we are getting wrong answers
moreover, its editorial has been removed now
I don’t know why my code is not working. Can anyone check I would be thankful.
CODE LINK: CodeChef: Practical coding for everyone
example of map as array please
I have added it above
what is ar[0]? im little bit confused due to java working of maps,please clarify
nice explanation…
logic behind count=count+1; can u explain?
Initially ar[0] will be equal to zero.
You can put any integer inside it, for example:
int x = 1;
ar[0] = x;
@vivek96 Dont confuse yourself with Maps. Use STL Vectors/ Lists and as you’d asked it on separate question, follow the same pattern.
Whenever you’ve found a disconnected node which is not visited you add a new component by count += 1; Suppose you start the loop at node 0 it will be disconnected as well as go through a possible DFS and mark all other nodes connected to node 0 as Visited. Next iteration would be for a node that is not connected to the initially taken node 0.
@ssaxena36 yes you are right, but it’s good to know maps too, will be helpful in some other problem.
@ssaxena36 can you please find out the bug in my solution?
Here’s the link : CodeChef: Practical coding for everyone
For an entire graph that is connected, suppose has N = 4, You’d do a DFS from node 0 and put count = 1 (1st iteration) while for next iterations of loop from i = 1 to i = 3 visited would be TRUE so there will be no DFS again and count shall remain to 1. In the end, your answer is count - 1 = 0 because all nodes have a path. Hope this simplifies all for you
Yes I agree, GPD -MAY17 couldn’t be solved without Maps though. You too had a good point. btw looking into your solution now.
but when i call dfs it will recursively done the dfs,when why i need to call everytime,please dont mind,because this is my first graph problem