Poj Solution 2838

http://poj.org/problem?id=2838

#include <stdio.h>


struct edge {
    edge *pri;
    edge *next;
};

edge *e[1010];
edge temp[1010][1010];

void add( int from, int to ) {
    temp[from][to].next = e[from];
    temp[from][to].pri = 0;
    if( e[from] ) e[from]->pri = temp[from]+to;
    e[from] = temp[from]+to;
}

void del( int from, int to ) {
    if( temp[from][to].pri )
        temp[from][to].pri->next = temp[from][to].next;
    if( temp[from][to].next )
        temp[from][to].next->pri = temp[from][to].pri;
    if( e[from] == temp[from]+to )
        e[from] = e[from]->next;
}

bool search( int from, int to ) {
    bool sign[1010] = { false };
    int qh = 0, qe = 0, q[1010], t, k;
    
    q[qh++] = from;
    sign[from] = true;

    while( qe < qh ) {
        t = q[qe++];
        for( edge *p = e[t]; p; p = p->next )
            if( !sign[k=p-temp[t]] ) {
                if( k == to )
                    return true;
                sign[k] = true;
                q[qh++] = k;
            }
    }

    return false;
}

int main( ) {
    int u, v, n, q;
    char c[2];
    scanf( "%d%d", &n, &q );
    while( q-- ) {
        scanf( "%1s%d%d", c, &u, &v );
        if( c[0] == 'I' ) {
            add( u, v );
            add( v, u );
        }
        else if( c[0] == 'D' ) {
            del( u, v );
            del( v, u );
        }
        else
            printf( "%cn", (u==v||search( u, v ))?'Y':'N' );

    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *