where to start solving graph theory problem

Hello everyone. I need some suggestions on where to begin solving graph theory problems. I have read some books and articles and am able to program bfs, dfs, spanning tree problems etc. But when it comes to solving programming contest problems, I cannot solve any problem.

I mean in books, we have questions like “print nodes of a graph in bfs manner (graph in adjacency list or matrix)”, but in programming contests,it is not the case.

I cannot even solve problems tagged easy. I was having similar problems in dp but now I can solve easy dp problems. But I am seriously lost in graph theory problems. Can anyone help me?

P.S. editorials tell logic of the problem but not how to solve them.Please give suggestions without any reference to editorials and wikipedia.

you have to start practicing to get perfection in solving problem…!
http://discuss.codechef.com/tags/graph/
You can get list of questions which you need to practice.

But as you are saying you can’t even solve one problem from easy, you might need to learn a bit more before trying, for this purpose refer this : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1

1 Like

try this:
http://e-maxx.ru/ There are 51 graph algorithms.Learn them and solve at least 5 problems for each algorithm.

4 Likes

It is a little difficult to use the site using google translater but I will give it my best. Thanks for providing the link. Its really helpful.

The topcoder site shows how to identify a problem and which algorithm to use. But it does not show how to implement it. I need resource that shows how to solve a problem in a programming language(preferably c). I don’t need solutions to all problems, just a little nudge in the right direction.

The best way is writing implementations on your own.But it takes some time.I have a code library which contains implementations for all algorithms in cpp.If you want it,give me your mail I will send it to you.Whatever you do understand it completely.

1 Like

if you are comfortable with maths try this:
Diestel, Graph Theory

Okay guys, after understanding graph searching algorithm, I tried solving my first problem http://www.codechef.com/problems/HDELIVER but got wrong answer. After reading the problem again and again, I solved some problems and I fixed them all. But I am still getting wrong answer. What can I do?

I am also posting the code :

``````           #include<stdio.h>
#include<list>
using namespace std;
int main()
{
int test,n,m,a,b,q,iter=1,k;
list<int> bfs;
scanf("%d",&test);
while(test--)
{
scanf("%d%d",&n,&m);
int graph[n][n],visited[n],color[n],loop[n];
for(int i=0;i<n;i++)
{
visited[i]=0;
color[i]=0;
loop[i]=0;
for(int j=0;j<n;j++)
graph[i][j]=0;
}
while(m--)
{
scanf("%d%d",&a,&b);
if(a==b)			//In case of loop,special array "loop" is                                                      checked
loop[a]++;
else
graph[a][b]=graph[b][a]=1;  //Graph has 1 if edge exists else 0
}
scanf("%d",&q);
for(k=0;k<n;k++)
{
if(!visited[k])
{
for(int i=0;i<n;i++)
{
if(graph[k][i])
bfs.push_back(i);
}
while(!bfs.empty())
{
int front=bfs.front();
for(int i=0;i<n;i++)
{
if(graph[front][i] && visited[i]==0)
{
visited[i]=1;
color[i]=iter;
bfs.push_back(i);
}
}
bfs.pop_front();
}
iter++;
}
}
while(q--)
{
scanf("%d%d",&a,&b);
if(a==b)
{
//printf("LOOP\n");
if(loop[a])
printf("YO\n");
else
printf("NO\n");
}
else
{
if(color[a]==color[b])
printf("YO\n");
else
printf("NO\n");
}
}
}
``````

}

I have got the answer , many thanks to Kunal Sheth [3934999] for pointing out my mistake. Now I have solved my very first graph theory program.