Advertisement
nontawat1996

ACM A Far Node

Mar 12th, 2012
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.06 KB | None | 0 0
  1. #include <stdio.h>
  2. int lookup(int x, int *n, int *a)
  3. {
  4.     int i;
  5.     for (i=0;i<*n; i++) if(a[i] == x) return i;
  6.     a[*n] = x;
  7.     ++*n;
  8.     return *n-1;
  9. }
  10. void touch(int ttl, int node, int con[][30], int n, int hit[])
  11. {
  12.     int i;
  13.     hit[node] = 1;
  14.     if (!ttl) return;
  15.     for (i=0; i<n; i++) if(con[node][i]) touch(ttl-1,i,con,n,hit);
  16. }
  17. int main()
  18. {
  19.     int c=1,i,j,k,m,con[30][30],nodes[30],n,n_con,hit[30];
  20.  
  21.     while(scanf("%d",&n_con),n_con)
  22.     {
  23.         for (i=0;i<30;i++) for(j=0;j<30;j++)con[i][j]=0;
  24.         n=0;
  25.         for(i=0;i<n_con;i++)
  26.         {
  27.             scanf("%d %d",&j,&k);
  28.             j=lookup(j,&n,nodes);
  29.             k=lookup(k,&n,nodes);
  30.             con[j][k]=con[k][j]=1;
  31.         }
  32.  
  33.         while(scanf("%d %d",&j,&k),j||k)
  34.         {
  35.             for(i=0;i<n;i++) hit[i]=0;
  36.             touch(k,lookup(j,&n,nodes),con,n,hit);
  37.             for(m=0,i=0;i<n;i++) if (!hit[i]) m++;
  38.             printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", c++, m, j, k);
  39.         }
  40.     }
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement