bfs competitve programming [on hold]











up vote
-5
down vote

favorite












Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf



    #pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);

}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);

}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];

}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}

for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");



}









share|improve this question













put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago


Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.











  • 2




    Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
    – kfx
    yesterday






  • 1




    ... and your link doesn't work anyway.
    – Jabberwocky
    yesterday















up vote
-5
down vote

favorite












Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf



    #pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);

}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);

}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];

}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}

for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");



}









share|improve this question













put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago


Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.











  • 2




    Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
    – kfx
    yesterday






  • 1




    ... and your link doesn't work anyway.
    – Jabberwocky
    yesterday













up vote
-5
down vote

favorite









up vote
-5
down vote

favorite











Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf



    #pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);

}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);

}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];

}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}

for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");



}









share|improve this question













Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf



    #pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);

}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);

}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];

}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}

for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");



}






c algorithm






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked yesterday









humblefool

436




436




put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago


Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.






put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago


Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.










  • 2




    Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
    – kfx
    yesterday






  • 1




    ... and your link doesn't work anyway.
    – Jabberwocky
    yesterday














  • 2




    Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
    – kfx
    yesterday






  • 1




    ... and your link doesn't work anyway.
    – Jabberwocky
    yesterday








2




2




Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday




Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday




1




1




... and your link doesn't work anyway.
– Jabberwocky
yesterday




... and your link doesn't work anyway.
– Jabberwocky
yesterday

















active

oldest

votes






















active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes

Popular posts from this blog

'app-layout' is not a known element: how to share Component with different Modules

android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

WPF add header to Image with URL pettitions [duplicate]