Problem Link-https://www.codechef.com/problems/TRATCK1
Please explain your approach for this problem.
Please tell me how to deal with problems as i am new to graph theory?
3 Likes
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
4 Likes
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.
2 Likes
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…
1 Like
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.
2 Likes
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.
2 Likes
@ssaxena36 can you please find out the bug in my solution?
Here’s the link : https://www.codechef.com/viewsolution/13900283
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
@vivek96 If you just call the dfs function once then it will only perform dfs in one component of the graph.
If there are more than one components then we will have to iterate and run dfs starting from other vertices too.
1 Like
sorry,its not your fault but im unable to understand the concept of components.feeling bad!
DFS : to identify a single component.
Re-iteration of the loop : to find out the nodes which are not connected to the previous component found out and search again.
@shraeyas Sorry I wasn’t able to figure out the bug but seems like that Map is causing problems. I’m more of a Java/Python user so can’t help much.