You see, I had a crazy time with this one. So no joke. I made my big mistake in designing the queue and finally used the STL.
Still, there are some really useful test cases I got. I corrected it later. It was in the empty verifier.
Input:
1Output:
1 1
25 0
1 0
1 1
0 0
5
1 2 2 3 3 4 4 5 6 7
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
0 0
0
Case 1: 0 nodes not reachable from node 25 with TTL = 0.
Case 2: 0 nodes not reachable from node 1 with TTL = 0.
Case 3: 0 nodes not reachable from node 1 with TTL = 1.
Case 4: 6 nodes not reachable from node 1 with TTL = 0.
Case 5: 5 nodes not reachable from node 1 with TTL = 1.
Case 6: 4 nodes not reachable from node 1 with TTL = 2.
Case 7: 3 nodes not reachable from node 1 with TTL = 3.
Case 8: 2 nodes not reachable from node 1 with TTL = 4.
Case 9: 2 nodes not reachable from node 1 with TTL = 5.
Case 10: 2 nodes not reachable from node 1 with TTL = 6.
Case 11: 2 nodes not reachable from node 1 with TTL = 7.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int q[100], front, rear, color[100], graph[100][100], g_depth, v[100], d[100], n_edge;
void init_q() { front = 0; rear = 0; }
void insert_q(int val) { q[rear++]=val; }
int del_q() { return q[front++]; }
int q_empty() { return (front==rear); }
int BFS(int src) {
int depth=1, count=0, i, u;
init_q();
insert_q(src);
for (i=1 ; i<=33 ; i++) {
color[i]=0;
d[i]=-1;
}
d[src]=0;
color[src]=1;
while (!q_empty()) {
u = del_q();
for (i=1 ; i<=33 ; i++) {
if (graph[u][i]==1 && color[i]==0) {
color[i]=1;
insert_q(i);
d[i]=d[u]+1;
}
}
}
for (i=1 ; i<=33 ; i++) {
if (d[i]>0 && d[i]<=g_depth) {
count++;
}
}
return count;
}
int main() {
int i, j, x, y, cases=1, node, p_x, p_y, k;
while (scanf("%d",&n_edge)&& n_edge) {
for (i=0 ; i<=33 ; i++) {
v[i]=-1;
for (j=0 ; j<=33 ; j++) {
graph[i][j]=0;
}
}
for (i=1, node=1 ; i<=n_edge ; i++) {
scanf("%d %d",&x,&y); /*----------Renaming method----------*/
for (k=1, p_x=-1; k<node ; k++) {
if (v[k]==x && p_x==-1) {
p_x=k;
break;
}
}
if (p_x<0) {
v[node++]=x;
p_x=node-1;
}
for (k=1, p_y=-1 ; k<node ; k++) {
if (v[k]==y && p_y==-1) {
p_y=k;
break;
}
}
if (p_y<0) {
v[node++]=y;
p_y=node-1;
}
graph[p_x][p_y]=graph[p_y][p_x]=1;
graph[p_x][p_x]=graph[p_y][p_y]=1;
}
while (scanf("%d %d",&x,&g_depth)) {
if (!x && !g_depth)
break;
for (i=1 ; i<=33 ; i++) {
if (v[i]==x) {
break;
}
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cases++,node-BFS(i)-2,x,g_depth);
}
}
return 0;
}
Same pinch buddy :P
ReplyDeleteUsed floyd warshall