Code: Select all
AC
Moderator: Board moderators
Code: Select all
AC
Code: Select all
#include<stdio.h>
int a,t,front,rear,level,nc,q[100000],i,j,k,l,m,n,x[10000][10000],y[10000],z[100000],state[10000];
int main()
{
scanf("%d",&nc);
for(l=1;nc!=0;l+=j-1)
{
for(i=0;i<10000;i++) x[i][0]=1;
t=0;
for(i=1;i<=nc;i++)
{
scanf("%d%d",&m,&n); //I have store all node I can go directly from a node(index) in two dimentional array
//x[m][0] indicates how many node I can go from node m.
if(x[m][0]==1) t++;
x[m][x[m][0]++]=n;
if(x[n][0]==1) t++;
x[n][x[n][0]++]=m;
}
scanf("%d%d",&y[1],&z[1]);
for(k=1;y[k]!=0||z[k]!=0;) scanf("%d%d",&y[k],&z[++k]);
for(j=1;j<k;j++)
{
for(i=0;i<10000;i++) state[i]=0; //initializing the state
rear=1;
front=1;
level=1;
a=0;
q[rear]=y[j];
n=y[j];
for(i=1;rear>=front&&a!=z[j];i++) //traversing the node.
{
state[n]++;
for(m=1;m<x[n][0];m++)
{
if(state[x[n][m]]==0)
{
q[++rear]=x[n][m],state[x[n][m]]++;
}
}
if(front==level) level=rear,a++;
n=q[++front];
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",l+j-1,t-rear,y[j],z[j]);
}
scanf("%d",&nc);
}
return 0;
}
Code: Select all
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int nc,nEdge,a,b,i,root,ttl,cases=1;
while(1)
{
vector<int>edges[10000];
cin>>nc;
if(nc==0)break;
for(i=0;i<nc;i++)
{
cin>>a>>b;
if(a==0&&b==0)break;
edges[a].push_back(b);
edges[b].push_back(a);
}
while(1)
{
int v,visited[10000]={0},dist[10000]={0},u,count=0,flag=0;
cin>>root>>ttl;
if(root==0&&ttl==0)
{
flag=1;
break;
}
queue<int>q;
q.push(root);
while(!q.empty())
{
v=q.front();
visited[v]=1;
for(i=0;i<edges[v].size();i++)
{
u=edges[v][i];
if(!visited[u])
{
visited[u]=1;
dist[u]=dist[v]+1;
if(dist[u]>ttl)count++;
q.push(u);
}
}
q.pop();
}
if(!flag)
cout<<"Case "<<cases<<": "<<count<<" nodes not reachable from node "<<root<<" with TTL = "<<ttl<<"."<<'\n';
cases++;
}
}
return 0;
}
Code: Select all
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
#include<utility>
#define L long long int
#define U unsigned long long int
using namespace std;
int arr[111][111];
map <int,int>m;
vector < pair<int,int> >v;
main()
{
int t = 1;
while(1)
{
int n,p=0;
cin>>n;
m.clear();
v.clear();
if(!n)
break;
for(int i = 0;i<n;i++)
{
int a,b;
cin>>a>>b;
if(!(a|b))
break;
//cout<<a<<b<<endl;
if(m.find(a) == m.end())
m.insert(make_pair(a,p++));
if(m.find(b) == m.end())
m.insert(make_pair(b,p++));
v.push_back(make_pair(a,b));
}
for(int i = 0;i<m.size();i++)
{
for(int j = 0;j<m.size();j++)
arr[i][j] = -1;
}
for(int i = 0;i<n;i++)
{
int a = m.find(v[i].first)->second ;
int b = m.find(v[i].second)->second;
arr[a][b] = 1;
arr[b][a] = 1;
}
for(int k = 0;k<m.size();k++)
{
for(int i= 0;i<m.size();i++)
{
for(int j = 0;j<n;j++)
{
if(i == j)
arr[i][j] = 0;
else if(arr[i][j] == -1)
{
if(arr[i][k] != -1 && arr[k][j] != -1)
arr[i][j] = arr[i][k] + arr[k][j];
}
else
{
if(arr[i][k] != -1 && arr[k][j] != -1)
arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
}
int src,ttl;
while(1)
{
cin>>src>>ttl;
if(!(src|ttl))
break;
int c = 0;
for(int i = 0;i<m.size();i++)
{
if(src == i)
continue;
int x = m.find(src)->second;
if(arr[x][i] > ttl || arr[x][i] == -1)
c++;
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",t++,c,src,ttl);
}
}
}
Code: Select all
if(src == i)
continue;
Code: Select all
#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<bitset>
#include<string>
#include <sstream>
#include <fstream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define pi 2*acos(0.0)
using namespace std;
int BFS(int start,int ttl);
vector<int>adj[40];
vector<int>vec;
map<int,int>mp;
int main()
{
int nc,node,i,f,u,v,j,start,ttl,t=0;
while(scanf("%d",&nc)==1)
{
if(nc==0) break;
f=0;
for(i=1;i<=nc;i++)
{
scanf("%d%d",&u,&v);
if(mp[u]==0)
{
mp[u]=++f;
vec.push_back(mp[u]);
}
if(mp[v]==0)
{
mp[v]=++f;
vec.push_back(mp[v]);
}
adj[mp[u]].push_back(mp[v]);
adj[mp[v]].push_back(mp[u]);
}
sort(vec.begin(),vec.end());
node=vec.size();
while(scanf("%d%d",&start,&ttl)==2)
{
int count;
if(start==0&&ttl==0) break;
int start1=start;
if(mp[start]==0)
{
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size(),start1,ttl);
continue;
}
start=mp[start];
count=BFS(start,ttl);
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size()-count,start1,ttl);
}
for(i=1;i<=node;i++)
adj[i].clear();
vec.clear();
mp.clear();
}
return 0;
}
int BFS(int start,int ttl)
{
int dist[50]={0};
int count=1,i;
map<int,int>mpp;
mpp[start]=1;
queue<int>q;
q.push(start);
while(!q.empty())
{
int u=q.front();
q.pop();
for(i=0;i<adj[u].size();i++)
{
int v=adj[u][i];
dist[v]=dist[u]+1;
mpp[v]++;
if(mpp[v]>1) continue;
if(dist[v]<=ttl)
count++;
if(dist[v]<=ttl-1)
q.push(v);
}
}
mpp.clear();
return count;
}
Code: Select all
2
1 1 1 2
1 1 0 0
0
Code: Select all
Case 1: 0 nodes not reachable from node 1 with TTL = 1.