UVA- 10859 - Placing Lampposts.

Problem Link :
 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=68&page=show_problem&problem=1800
Solution : C++

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int jannath=1000+10;
const int love=2000;
int imon[jannath][2];
bool heaven[jannath][2];
vector<int> Ctg[jannath];

int dp(int i,int j,int f)
{
    if(heaven[i][j]) return imon[i][j];
    heaven[i][j]=1;
    int& ans=imon[i][j];
    ans=love;
    int distance=Ctg[i].size();
    for(int u=0; u<distance; u++)
    {
        int v=Ctg[i][u];
        if(v!=f)
        {
            ans +=dp(v,1,i);
        }
    }
          if(f!=-1 && !j) ans++;
    if(f==-1 || j)
    {
        int sum=0;
        for(int u=0; u<distance; u++)
        {
            int v=Ctg[i][u];
            if(v!=f)
            {
                sum +=dp(v,0,i);
            }
        }
              if(f!=-1) sum++ ;
        ans=min(ans,sum);
    }
    return ans;
}
int main()
{
    int T, N, M, i, u, v;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &M);
        for(i = 0; i < N; i++) Ctg[i].clear();
        for(i = 0; i < M; i++)  
        {
            scanf("%d%d", &u, &v);
            Ctg[u].push_back(v);
            Ctg[v].push_back(u);
        }
        memset(heaven, 0, sizeof(heaven));
        int ret = 0;
        for(i = 0; i < N; i++)
            if(!heaven[i][0]) ret += dp(i, 0, -1);
        printf("%d %d %d\n", ret/love, M-ret%love, ret%love);
    }
    return 0;

}