UVa : 336 (A Node Too Far)


// 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
Advertisements

6 thoughts on “UVa : 336 (A Node Too Far)

  1. 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

  2. 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;
    }

  3. //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;
    }

  4. #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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s