Mar-Apr 2011: Airline Comparison

An Railway Reservation deprtment document contains a list of trains between pairs of stations. A trip may be built by sequencing trains. Two railway operators are equivalent if they offer connections between the same pairs of stations, irrespective of the number of scales in between.

Problem

Given the catalogs of two railway operators, determine if they are equivalent or not.

Input

The input begins with a single positive integer on a line indicating the number of the cases following. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input contains:

First line: the number N of sequencing trains in the catalog of the first company;
N subsequent lines: two characters separated by one space, for the names of the origin and destination stations of a train;
Line N+2: the number M of trains in the catalog of the second company;
M subsequent lines: two characters separated by one space, for the names of the origin and destination stations of a train.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

One line containing YES or NO

Sample Input

1

6
A B
B E
A E
C F
E C
D A
7
A B
D A
E C
C F
D B
B E
D F

Sample Output

YES

Algorithm

It is a simple graph matching problem. make the disjoint set of first graph and match the second graph with it.  
start  
for all edge in graph g1  
make_set(e);  
for all edge in graph g2  
    x=find_set(u);  
    y=find_set(v);  
    if(x!=y)  
       Print-> NO;  
       return;  
print->YES;  
return;

Algorithm Description

C Code

/** Code Written By: Ankit Babbar
    Date: 26 March,2011
    Quesn: Airline Comparison
**/

#include
#define MAXN 302

int R[MAXN], P[MAXN];
int r[MAXN], p[MAXN];

struct ss{
    int u, v;
}edge[100000];

void Ini() {
    int i;
    for(i = 0; i< 300; i++) {
        p[i] = P[i] = i;
        r[i] = R[i] = 0;
    }
}

int FindSet(int s) {
    if(s != P[s])
        P[s] = FindSet(P[s]);
    return P[s];
}

int Find(int s) {
    if(s != p[s])
        p[s] = Find(p[s]);
    return p[s];
}

void Link(int x, int y) {
    if(R[x]>R[y])
        P[y] = x;
    else {
        P[x] = y;
        if(R[x] == R[y])
            R[y]++;
    }
}

void Link1(int x, int y) {
    if(r[x]> r[y])
        p[y] = x;
    else {
        p[x] = y;
        if(r[x] == r[y])
            r[y]++;
    }
}

void MakeLink(int x, int y) {
    int u, v;
    u = FindSet(x);
    v = FindSet(y);
    if(u != v)
        Link(u, v);
}

void Make(int x, int y) {
    int u, v;
    u = Find(x);
    v = Find(y);
    if(u != v)
        Link1(u, v);
}

void Final(int n) {
    int i, u, v, nott = 0;
    for(i = 0; i< n; i++) {
        u = Find(edge[i].u);
        v = Find(edge[i].v);
        if(u != v){
            nott = 1;
            break;
        }
    }
    if(nott) printf("NO\n");
    else printf("YES\n");
}

void Cal(int m, int n) {
    int i, u, v, nott = 0;
    char temp[10], dum[10];
    for( i = 0; i< m; i++) {
        scanf("%s%s",temp,dum);
        if(nott) continue;
        u = temp[0];
        v = dum[0];
        u = FindSet(u);
        v = FindSet(v);
        if(u != v)
            nott = 1;
        Make(temp[0], dum[0]);
    }
    if(nott) {
        printf("NO\n");
        return;
    }
    Final(n);
}

int main() {
    freopen("input.txt","r",stdin);
    int kases, i, n, m, u, v;
    char temp[10], dum[10];
    scanf("%d",&kases);
    while(kases--) {
        Ini();
        scanf("%d",&n);
        for(i = 0; i< n; i++) {
            scanf("%s%s",temp,dum);
            u = temp[0];
            v = dum[0];
            edge[i].u = u;
            edge[i].v = v;
            MakeLink(u,v);
        }
        scanf("%d",&m);
        Cal(m, n);
        if(kases) {
            printf("\n");
        }
    }
}
By admin | March 13, 2019 | Graduate . Under Graduate | 0 Comments |

Next

Stacking Boxes