280 - Vertex

[Fakhrul Abedin]

Hi,
I received Runtime error whenever I use malloc() for Dynamic memory allocation in C. The same code is accepted if I use static array. I don't know if I use malloc in wrong way. How can I do Dynamic memory allocation in C that won't yield RTL?

Here is a sample code of my malloc use

Code: Select all

	
#include<stdlib.h>
/*Allocating memory for graph*/
		G=(int **) malloc((size_t) sizeof(int *)*n);
		for(loop=1;loop<=n;loop++){
			G[loop]=(int *) malloc((size_t) sizeof(int)*n);
			nonaccessible[loop]=1;
		}
		/*End of allocation*/

Thanks.

[mf]

You allocate an array of size n (indexed 0 to n-1), but try to write to its elements with indexes 1 to n. The last one doesn't exists, and write to it probably corrupts some of allocator's internal data.

how to do DMA in C

Acronym DMA usually stands for "Direct Memory Access", a thing from OS and hardware worlds.

[Fakhrul Abedin]

Thanks. Yes DMA is an OS staff, I can remember, but here I used it (erroneously) as a shortcut of dynamic memory allocation, not as the acronym of Direct Memory Access.

Your point is right but you will find the RTL even if you use index range between 0 - (n-1) or allocate memory n+1.

My question is if at all malloc funtion can be used in UVA online judege. Or what is the way of dynamic memory allocation in UVA O J.

Regards

[mf]

Yes, malloc() is allowed.

The way you use it is correct, if you either fix your loop to go from 0 to n-1, or allocate n+1 elements.

[Fakhrul Abedin]

Thank you big brother for your great info.

I am posting here the code for 280 - Vertex where I used malloc, in Linux I don't find any runtime crash but after submission i got RTL. Would you kindly review and help me to find my fault?

Code: Select all

#include<stdio.h>
#include<stdlib.h>

short nonaccessible[101];
int **G,count;

void  DFS_VISIT(int n,int i,int adj[]){
	int v;
	for(v=1;v<=n;v++){
		if( !(adj[v]^1) ){
			if( !(nonaccessible[v]^1) ){
				nonaccessible[v]=0;
				count++;
				DFS_VISIT(n,v,G[v]);
			}
		}
	}
}

main(){
	int n,loop,i,j,visited;
	while(scanf("%d",&n) && n){
		/*Allocating memory for graph*/
		G=(int **) malloc((size_t) sizeof(int *)*(n+1) );
		for(loop=1;loop<=n;loop++){
			G[loop]=(int *) malloc((size_t) sizeof(int)*(n+1) );
			nonaccessible[loop]=1;
		}
		/*End of allocation*/
		
		/*Generating Graph*/
		scanf("%d",&i);
group:
		while(scanf("%d",&j) && j){
			G[i][j]=1;
		}
		if(scanf("%d",&i) && i)
			goto group;		
		/*End Generating Graph*/

		/*Input of nodes for investigation*/
		scanf("%d",&j);
		/*Start of investigation*/
		while(j--){
			scanf("%d",&i);
			count=0;
			DFS_VISIT(n,i,G[i]);
			printf("%d",n-count);
			for(loop=1;loop<=n;loop++)
				if(nonaccessible[loop])
					printf(" %d",loop);
			printf("\n");
			for(loop=1;loop<=n;loop++)
				nonaccessible[loop]=1;
		}/*End of Investigation*/
	}
}

[mf]

You don't need malloc there, "int G[101][101];" will do just fine.

If you still want to use malloc, then don't forget that you have to free() every piece of memory that you've malloc()ed.

[theharshest]

I am getting TLE for following code
Please help

Code: Select all

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int main()
{
	int n,t,k,x,y;
	vector< vector<int> > mat; // adjacency matrix
	vector<bool> vis; // visited nodes

	cin>>n;

	while(n!=0)
	{
		vis.resize(n,0);
		scanf("%d",&t);
		mat.resize(n);
		for(int i=0;i<n;i++)
			mat[i].resize(n,-1);	


		while(t!=0)
		{
			scanf("%d",&k);
			while(k!=0)
			{
				mat[t-1][k-1]=1;
				scanf("%d",&k);
			}
			scanf("%d",&t);
		}

		scanf("%d",&x);

		while(x--)
		{
			for(int i=0;i<n;i++)
				vis[i]=0;	

			scanf("%d",&y);

			stack<int> s;

			for(int i=0;i<n;i++)
				if(mat[y-1][i]==1)
				{
					s.push(i);
					break;
				}

			// applying dfs
			while(!s.empty())
			{				
				int tmp=s.top();
				vis[tmp]=1;
				s.pop();
		
				for(int i=0;i<n;i++)
					if(mat[tmp][i]==1 && !vis[i])
						s.push(i);	
			}

			vector<int> ans; // stores all unvisited nodes

			for(int i=0;i<n;i++)
				if(!vis[i])
					ans.push_back(i);

			printf("%d",(int)ans.size());

			sort(ans.begin(),ans.end());

			for(int i=0;i<ans.size();i++)
				printf(" %d",ans[i]+1);
			printf("\n");
		}	
		
		scanf("%d",&n);
	}
}

[shreyarora]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
int main()
{
int n,i,*c,l,x,k,w=0,j;
long int p,q,args;
char *a,*b,temp;
scanf("%d",&n);
a=(char *)malloc(1000*(sizeof(char)));
b=(char *)malloc(1000*sizeof(char));
c=(int *)malloc(10000*sizeof(int));
for(i=0;i<n;i++)
{
scanf("%s",a);
scanf("%s",b);
l=strlen(a);
q=l/2;
x=strlen(b);
p=x/2;
for(j=0,k=(l-1);j<q;j++,k--)
{
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
for(j=0,k=(x-1);j<p;j++,k--)
{
temp=b[j];
b[j]=b[k];
b[k]=temp;
}

p=atol(a);
q=atol(b);
args=(p+q);
while(args!=0)
{
k=(int)args%10;
c[w]=k;
args=args/10;
w++;
}
c[w]='^';
w++;

}
c[w]='$';
for(i=0;;)
{
if(c==0)
i++;
else
break;
}
for(i=i;c!='$';i++)
{
if(c=='^')
printf("\n");
else
printf("%d",c);
}
return 0;
}

[calicratis19]

AC

[looserdgr8]

Please someone help me. I have run every I/O in this forum. Every thing seems okay. But still i get wrong answer. I use BFS algorithm.
Here is my code:

Code: Select all

Accepted. Array size upgraded to 500

[looserdgr8]

Please anyone H-E-L-P me. I am now frustrated. Anyone check my code please............>>>

[looserdgr8]

Anyone please help me.

[calicratis19]

@looserdgr8 increase the size of the defined constant 'size'. u will get ac.

[looserdgr8]

Thanx calicratis19. Its AC

[calicratis19]

@looserdgr8, u should remove your code.thanks.