galactik.. giving WA. plz help

#include
#include
#include
#include
using namespace std;

const int maxN = 100010;
vector<int> a[maxN];
vector<int> x;
int mark[maxN];
int value[maxN];
int mini=10000000;

void dfs(int u)
{
	mark[u]=1;
	if(value[u] < mini && value[u]>=0)
	mini= value[u];

	for(int i=a[u].size();i--;)
	{
		int v=a[u][i];
		if(!mark[v]) dfs(v);
	}
}

int main()
{
		int n,m,flag=0,minx=0;
		scanf("%d%d",&n,&m);

		int i,u,v;
		long long sum=0;
		for(i=0;i<n;i++) {
		    a[i].clear();
		    mark[i]=0;
		}
		for(int k=0;k<m;k++)
		{
			scanf("%d%d",&u,&v);
			a[u-1].push_back(v-1);
			a[v-1].push_back(u-1);
		}
		for(i=0;i<n;i++) scanf("%d",&value[i]);

        if(n<2)
		{
		    printf("0\n");
		    return 0;
		}

		for(i=0;i<n;i++)
		{
			if(!mark[i])
			{
                mini=10000000;
				dfs(i);
				if(mini==10000000)
				flag=1;
				else
                x.push_back(mini);
			}
		}

        if(flag==1)
        {
            printf("-1\n");
        }
        else
        {
            for(i=0;i<x.size();i++)
            {
                sum= sum+ x[i];
                if(x[i]<minx)minx= x[i];
            }

            sum+= (x.size()-2)*minx;
            printf("%lld\n",sum);

        }
	return 0;
}

Check your output for this test case:

2 1

1 2

-1

-2

Your Output : -1

Correct Output: 0

1 Like

still giving WA

You must end your program after you print -1…your program seems to continue to print other values after printing -1.

1 Like

still WA

@shashank_1…your code fails for this testcase

INPUT:

3 2
2 3
1 2
-1 
-1
-1

This is because…If there is ONE compenent in the graph and all are interconnected then there is not need to build any teleport hence the o/p should be 0 instead of -1.Hope this helps.:smiley:

1 Like

@shashank_1: there were two bugs in your code:

  1. when the whole graph visited in one go, u was still printing -1, instead of 0(that u fixed probably,actually I am not able to access your latest ideone submission).
  2. the second bug is that, u have not initialized the variable minx, with any max_value before making the comparison.

Below is the link of your modified code, which got AC.
http://www.codechef.com/viewsolution/2384944

1 Like

thnx @ravishanker
u r right , thnx a lot…

bcoz of u, i m able to noe my mistake and correct it
nw i hv done dis ques using disjoint-set structure
http://www.codechef.com/viewsolution/2385176

here is the link to my solution CodeChef: Practical coding for everyone
gettin right answer for all above testcases bt getting WA plz help

@shashank_1: thnks, good going :slight_smile: