UVa : 336 (A Node Too Far)
July 2, 2010 5 Comments
// http://uva.onlinejudge.org/external/3/336.html
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <bitset>
#include <utility>
#include <set>
#define pi acos(-1.0)
#define N 1000000
using namespace std;
bool matrix [30 + 3] [30 + 3];
void reset ()
{
for ( int i = 0; i < 33; i++ )
memset (matrix [i], false, sizeof (matrix [i]));
}
int main ()
{
int edges;
int cases = 0;
while ( cin >> edges && edges ) {
reset ();
map <int, int> index;
int nodeNumber = 1;
for ( int i = 0; i < edges; i++ ) {
int a, b;
cin >> a >> b;
if ( !index [a] ) index [a] = nodeNumber++;
if ( !index [b] ) index [b] = nodeNumber++;
matrix [index [a]] [index [b]] = matrix [index [b]] [index [a]] = true;
}
int queryNode;
int ttl;
int dist [30 + 3];
while ( cin >> queryNode >> ttl ) {
if ( queryNode == 0 && ttl == 0 ) break;
memset (dist, -1, sizeof (dist));
dist [index [queryNode]] = 0;
queue <int> q;
q.push (index [queryNode]);
while ( !q.empty () ) {
int pop = q.front ();
q.pop ();
for ( int i = 1; i < nodeNumber; i++ ) {
if ( matrix [pop] [i] && dist [i] == -1 ) {
dist [i] = dist [pop] + 1;
q.push (i);
}
}
}
int cnt = 0;
for ( int i = 1; i < nodeNumber; i++ ) {
if ( dist [i] == -1 || dist [i] > ttl ) cnt++;
}
printf ("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
++cases, cnt, queryNode, ttl);
}
}
return 0;
}
// @END_OF_SOURCE_CODE
BFS Algorithm applied.
1. Line: 40, 46, 47, 49
i have used a map data structure under STL in C++
for example, if there are 5 nodes then the problem setter can mark them like, 50000, 234221, 239946, 393910, 2234
so i mapped them like this
50000 => 1
234221 => 2
239946 => 3
393910 => 4
2234 => 5
2. the graph is bidirectional, that means, if you can go from node ‘A’ to ‘B’ then
you can also go from node ‘B’ to ‘A’
matrix [index [a]] [index [b]] = matrix [index [b]] [index [a]] = true;
3. int dist [30 + 3];
the array contains the time you need to reach a particular node from queryNode.
for example, if queryNode = 5
dist [5] = 0;
// there is no cost from 5 to 5
if dist [6] == 1;
// this means, you can go from 5 to 6 with TTL 1
i initialized the dist array with -1.
4. then i applied the BFS algorithm
5. finally i loop through every node and look up the dist array
Line: 80-82
if a particular node is not possible to reach using given TTL then i increased a cnt variable by 1
cant we solve it by floyd warshall…
I tried it by floyd warshall ….but not accepted ..I checked almost every test cases …n mine code is correct but not accpted by judge ..plz help
#include
#include
#include
#include
#include
# define MAX 100
int outputcase=1;
const int INF= 99999999;
int pathmatrix[MAX][MAX];
using namespace std;
int main()
{
int E,N,costmatrix[MAX][MAX];
while(cin>>E && E)//#include ctsring
{
//———cost matrix initialisation———————-
for(int i=0;i<55;i++)
{
for(int j=0;j<55;j++)
{
costmatrix[i][j]=INF;
}
}
//———————————————————-
map index;
int nodeNumber=1;//starting Node number
for ( int i = 0; i > a >> b;
//cout<<"index [a]"<<index [a]<<endl;
if (!index [a] )
{
index [a] = nodeNumber++;
}
if (!index [b] )
{
index [b] = nodeNumber++;
}
costmatrix[index [a]] [index [b]] =costmatrix[index [b]] [index [a]] =1;
}
N=nodeNumber-1;//Number of vertices numbered from 1 to N;
//———path matrix initialisation———————-
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(costmatrix[i][j] !=INF && costmatrix[i][j] !=0 )
{
pathmatrix[i][j]=j;
}
else
{
pathmatrix[i][j]=0;//if the vertex starts from zero then here we give -1
}
}
}
//—————————————————————–
//——Floyd-Warshall All-Pairs Shortest Path———————
for(int k=1;k<=N;k++)
{
for(int i=1;i<=N;i++)
{
for(int j=1;j> q >> TTL )
{
if ( q == 0 && TTL == 0 ) break;
int count=0;
for(int j=1;jTTL && costmatrix[index[q]][j]!=TTL )
{
count=count+1;
}
}
}
cout<<"Case "<<outputcase<<": "<<count<<" nodes not reachable from node "<<q<<" with TTL = "<<TTL<<"."<<endl;
outputcase=outputcase+1;
}
}
system("pause");
return 0;
}
//I changed the algorithm frm floyd to bfs and it worked thanks TAUSIQ learned a lot frm this post
#include
#include
#include
#include
#define MAX 35
int dis[MAX];
int cases=0;
using namespace std;
struct node
{
int data;
node *next;
};
class breadth_first_search
{
private:
int visited[MAX];
int parent [MAX];
queue q;
public:
breadth_first_search();
node* getnode(int value)
{
node* iterator;
iterator=new node;
iterator->data=value;
iterator->next=NULL;
return iterator;
}
void adjacencylist(int edges);
void bfs(node* *arraypointer,int vertex)
{
node *temp;
temp=*(arraypointer+vertex);
while(temp!=NULL)
{
if(visited[temp->data]==0 && parent[vertex]!=temp->data)
{
q.push(temp->data);
visited[temp->data]=1;
parent [temp->data]=vertex;
}
temp=temp->next;
}
//——–When temp is NULL———————–
if(temp==NULL)
{
int element_under_popped=q.front();
dis[element_under_popped]=dis[parent[element_under_popped]]+1;
q.pop();
if(q.empty())
{
return;
}
else
{
//cout<<"bfs search is with"<<q.front()<<endl;
bfs((arraypointer),q.front());
return;
}
}
//——–temp==NULL condition ends—————————–
}
};
breadth_first_search::breadth_first_search()
{
for(int i=0;i<MAX;i++)
{
visited[i]=0;
parent [i]=-1;//-1 is like space
dis[i]=-1;
}
}
void breadth_first_search::adjacencylist(int edges)
{
node *arr[MAX],*it,*temp;
int m[MAX][MAX],N;
//—————–cost matrix initialisation—————–
for(int i=0;i<MAX;i++)
{
for(int j=0;j<MAX;j++)
{
m[i][j]=0;
}
}
//————————————————————
int nodeNumber=1;
map index;
for(int i=0;i> a >> b;
if ( !index [a] ) index [a] = nodeNumber++;
if ( !index [b] ) index [b] = nodeNumber++;
m[index [a]] [index [b]] = m[index [b]] [index [a]] = 1;
}
N=nodeNumber-1;
for(int i=1;i<=N;i++)
{
vectorv;
for(int j=1;j>m[i][j];
if(m[i][j]==1)
{
v.push_back(j);
}
}
//so the vector v contains that columns number(of row i) whose data is 1
if(v.size()!=0)
{
it=getnode(v[0]);
arr[i]=it;
for(int k=1;knext=it;
}
}
else
arr[i]=NULL;
}
int quer,TTL,querynode;
while ( cin >> quer >> TTL )
{
if ( quer == 0 && TTL == 0 ) break;
cases=cases+1;
querynode=index[quer];
parent[querynode]=querynode;
dis[querynode]=-1;
q.push(querynode);//start vertex should only be pushed into queue but should not be marked as visited
bfs(arr,querynode);
int counter=0;
for(int i=1;i TTL))
{
counter=counter+1;
}
}
cout<<"Case "<<cases<<": "<<counter<<" nodes not reachable from node "<<quer<<" with TTL = "<<TTL<<"."<<endl;
//—————————Reinitialisation for another test cases———————–
for(int i=0;i>edges && edges)
{
breadth_first_search b;
b.adjacencylist(edges);
}
//system (“pause”);
return 0;
}
I am really confused right now, I made it totally different. I think I will use your ideas guys. Thank you!
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
map<int, vector >Adj;
mapm;
queue q;
int N,E,i,j,u,x,y,source,vi[10000],d[10000],ttl;
void input()
{
Adj.clear();
m.clear();
int track=1;
cin>>E;
if(E==0) return;
for(i=0;i>x>>y;
if(m[x]==0) m[x]=track++;
if(m[y]==0) m[y]=track++;
Adj[m[x]].push_back(m[y]);
Adj[m[y]].push_back(m[x]);
}
}
int bfs(int,int)
{
memset(vi,0, sizeof vi);
memset(d,0, sizeof d);
int count=0;
q.push(m);
vi[m]=1;
d[m]=0;
while(!q.empty())
{
u=q.front();
q.pop();
for(j=0;jttl) count++;
vi[v]=1;
q.push(v);
}
}
}
return count;
}
int main()
{
freopen(“336in.txt”,”r”,stdin);
freopen(“336out.txt”,”w”,stdout);
int answer,co=1;
l:
input();
while(cin>>source>>ttl)
{
if(source==0 && ttl==0) goto l;
answer=bfs(m,ttl);
cout<<"Case "<<co++<<" : "<<answer<<" nodes not reachable from node "<<source<<" with TTL = "<<ttl<<"."<<endl;
}
return 0;
}
// Why My one is getting WA?