Answer to "All Graphs are not Trees"

A graph is said to be a tree when it has no cyclic path in it .

So the program focuses to find out whether the given graph is acyclic

by using a two dimensional array of size m*n.

Each row contains the max limit of array,start node and the adjacent nodes from

the previous node.Last index is a flag which is used in case of undirected graph

as here.

In undirected graph when 1-2 is the edge , there is an edge also from 2-1.

Eg :-we prove that the graph 

given by the input :

3 3

1 2

1 3

2 3

is cyclic  as shown in the diagram.

 If for any row , the first and the last element are same,

then the graph is cyclic,that is not a tree.Here in the second row ,node 2 comes 

in front and rear.

The program is described as follows..

#include<stdio.h>

#include<stdlib.h>

 

void print( int **a,int n, int m)

{

  int i,j;

 

  for(i=0;i<n;i++)

    {

      for(j=0;j<a[i][0];j++)printf("%d ",a[i][j]);

      printf("\n");

    }

  printf("\n");

 

}

 

int main()

{

  int n,m,i,j,k,r,c,**a,flag=0,temp,*pos;

 

  scanf("%d%d",&n,&m);

  pos=(int *)malloc(n*sizeof(int));

  a=(int **)malloc(n*sizeof(int *));

  for(i=0;i<n;i++)a[i]=(int *)malloc((m+2)*sizeof(int));

 

  for(i=0;i<n;i++){ a[i][1]=i+1; a[i][0]=2;}

 

 

  for(i=0;i<m;i++)

    {

  scanf("%d%d",&r,&c);

  for(k=0;k<n;k++)pos[k]=0;

 if(r==c){ flag=1; break;}

  if(r!=c)

    {

 for(j=0;j<n;j++)

    {

 

      if(a[j][a[j][0]-1]==r){ a[j][a[j][0]]=c; a[j][0]++; pos[j]=1;  }  

   }

 for(j=0;j<n;j++)

    {

     if(pos[j]==0&&a[j][a[j][0]-1]==c){ a[j][a[j][0]]=r; a[j][0]++; }     

    }  

print(a,n,m);

    }

    }

  if(flag==1){printf("NOT A TREE\n"); return 0; }

for(i=0;i<n;i++)

  {

if(a[i][0]>2&&a[i][1]==a[i][a[i][0]-1]){printf("YES\n"); return 0;}

  }

printf("TREE\n");

 

}

All Graphs are not Trees.

You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.

The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph . Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).

Example 1

Input:
3 2
1 2
2 3


Output:
TREE

Example 2
Input:
3 3
1 2
1 3
2 3

Output:
NOT A TREE

answer-anagram

/* ---This program works for string consisting of alphabets and numbers ---*/
#include<stdio.h>
#include<string.h>
#include<ctype.h>
main()
{
char input[80],output[80],index[62];
int i;
printf("Enter original string:");
scanf("%s",input);

for(i=0;i<62;i++)index[i]=0;

for(i=0;i<strlen(input);i++)
  {
    if(isalpha(input[i]))
      {
if(isupper(input[i]))index[input[i]-39]++;
else index[input[i]-97]++;
     }

    else if(isdigit(input[i]))index[input[i]+4]++;
  }
printf("Enter string to be checked:");
scanf("%s",output);

for(i=0;i<strlen(output);i++)
  {
    if(isalpha(output[i]))
      {
if(isupper(output[i]))index[output[i]-39]--;
else index[output[i]-97]--;
     }

    else if(isdigit(output[i]))index[output[i]+4]--;
  }


for(i=0;i<62;i++)if(index[i]){ printf("Not Anagram\n"); return;}

printf("Anagram\n");

}

Anagram of a string

You are given two strings S1 and S2, your task is to determine whether one string is an anagram of the other. 
An anagram of a string is a string obtained by permuting the letters of a string. 
For example aaba and aaab are anagrams, while abcd and deba are not.

answer for subset construction

#include<stdio.h>


void increment(int a[],int i)    //increments the bitvector by 1
{

if(a[i]==0||i==0)
{
a[i]=1;
return;
}
else
{
a[i]=0;
increment(a,i-1);
}
}


void print_subsets(int numbers[],int bitvector[],int n)  //prints all the subsets of a set
{
int i,j,count=1;

for(i=1;i<=n;i++)count=count*2;  //find no of subsets
printf("No of subsets=%d\n",count);
for(i=0;i<n;i++)bitvector[i]=0;   //initialise the bit vector

printf("{ }\n");  // null set is always present
for(i=1;i<count;i++)
{
increment(bitvector,n-1);      
printf("{ ");
for(j=0;j<n;j++) //scan the bit vector and print the corresponding number if its bit is set
{
if(bitvector[j]==1)printf("%d ",numbers[j]);
}
printf("}\n");
}

}

main()
{
int n,i,a[10],bitvector[10];
printf("Enter no of elements:\n");
scanf("%d",&n);

printf("Enter the elements:\n");
for(i=0;i<n;i++)scanf("%d",&a[i]);

print_subsets(a,bitvector,n);

}

All the subsets of a set of numbers

Write a program to print all the subset of a set of numbers.
The original set of numbers is read from the user.

Eg :-
input :1 2 3
output :.{NULL,1,2,3,12,13,23,123}

input : 0 1
output :{NULL,0,1,01}

answer to question on feb 25

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<dos.h>
int main()
{
char str[80],output[80],*p;
int i;
clrscr();
printf("Enter the sentence\n");
gets(str);
p=strtok(str," .");
strcpy(output,p);
strcat(output," ");
clrscr();
printf("%80s",output);
while(1)
{
delay(1000);
p=strtok(NULL," .");
if(p!=NULL)
{
strcat(output,p);
strcat(output," ");
clrscr();
printf("%80s",output);
}
else break;
}
for(i=75;i>0;i=i-5)
{
delay(1000);
clrscr();
printf("%*s",i,output);
}

getch();

return 0;


}

Question of the day

Write a program to display a moving sentence 
which is taken from the user as input.


The movement should be from right to left.


The sentence should be moving continuously
 and should reappear on termination

answers to quesion on Feb 23

The question was :
Write a program to determine whether an input string has unique characters or not using atmost two primitive data structures ?


[ Hint : primitive data structure may be integer,character. ]


It can be done by using recursive approach.
The code is given below :



#include<stdio.h>
#include<string.h>
char str[30];
int i;
void check(char a,int x)
{
if (a=='\0')
{
printf("\n all the charachers are unique\n");
getch();
exit (0);
}
for (i=x-1;i>=0;i--)
{
if (a==str[i])
{
printf("\nall characters are not unique");
printf("\n '%c' is being repeated\n",a);
getch();
exit(0);
}
}
check(str[x+1],x+1);
}




main()
{
clrscr();
printf("\n enter the string :");
scanf ("%[^\n]",str);
check(str[0],0);
return 1;
}

Quesion of the day

Write a program to determine whether an input string has unique characters or not using atmost two primitive data structures other than the string?

[ Hint : primitive data structure may be integer,character. ]