Gossiping

There was a public bus transport in one town. All buses had circular lines. Each line had at least two stops. Some lines had some stops in common. When two or more bus drivers met on some stop they announced each other all news they knew, so that after leaving the stop they all knew the same news. All drivers started driving their buses at the same time and at this time each driver knew some news that was not known to any other driver. Each bus ran all the time along a fixed bus line. Different buses running along the same bus line started possibly on different stops of the bus line at the beginning.

The operation of buses was highly synchronized. The time necessary to get from one stop to next stop was equal for all stops and all lines.

There were n lines ( 0 < n < 20), d drivers (and also d buses) ( 0 < d < 30) numbered by integers from 1 to d, and s bus stops ( 0 < s < 50) numbered by integers from 1 to s.

The drivers' gossiping club would like to know whether each driver, in some time, would learn all news from his colleagues. Write a program that will answer this question.

Input 

The input file consists of blocks of lines. Each block except the last describes one town. In the first line of the block there are integers n, d and s described above separated by one space. The next 2n lines contain descriptions of n bus lines (2 lines for each bus line) as follows: In the first line there are stop numbers on the corresponding bus line separated by one space. The stops are listed in the order the bus passes them. After passing the last stop listed on the line the bus goes again to the first stop listed on the line. The second line describes on which stops the individual buses operating on the bus line started at the beginning. The description consists of pairs s_i, d_i, where s_i is a stop number on the bus line and d_i is the number of driver driving the bus. All numbers s_i, d_i on the line are separated by one space. The last block consists of just one line containing 0 0 0, i.e. three zeros separated by one space.

Output 

The output file contains the lines corresponding to the blocks in the input file. A line contains Yes if the corresponding block in the input file describes a situation where each driver will learn, in some time, all news from his colleagues. Otherwise it contains No. There is no line in the output file corresponding to the last ``null'' block of the input file.

Sample Input 

2 3 5
1 2 3
1 1 2 2
2 3 4 5
2 3
0 0 0

Sample Output 

Yes

---

題目描述：

有一些公車司機在傳八卦，只有在他們同時在同一個站時，他們才會交頭接耳地傳遞。

問是否能將所有訊息傳遞出去。

題目解法：

每個公車路線上的點不會重複，那麼建一張圖表示 g[i][j] i 號司機與 j 號司機是否有可能碰面，

最後檢查是否只存在一個 component，又或者任兩點都可以傳遞。

對於有可能碰面的處理，由於每一個時刻移動的站數都一樣，對於 (p, q) 即一開始兩個司機的所在地點，

接下來求 (p', q')，使用 bfs 拓展，直到存在 p == q，或者無法找到任何一個存在的碰面地點。


#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> route[25];
int driver[35][2];
int sol(int d1, int d2) {
    int dp[55][55] = {};
    int i, j, k;
    int s1, s2, ns1, ns2, r1, r2;
    queue<int> S1, S2;
    r1 = driver[d1][1], r2 = driver[d2][1];
    S1.push(driver[d1][0]), S2.push(driver[d2][0]);
    while(!S1.empty()) {
        s1 = S1.front(), S1.pop();
        s2 = S2.front(), S2.pop();
        if(s1 == s2)
            return 1;
        for(i = 0; i < route[r1].size(); i++)
            if(route[r1][i] == s1)
                ns1 = route[r1][(i+1)%route[r1].size()];
        for(i = 0; i < route[r2].size(); i++)
            if(route[r2][i] == s2)
                ns2 = route[r2][(i+1)%route[r2].size()];
        if(dp[ns1][ns2])
            continue;
        dp[ns1][ns2] = 1;
        S1.push(ns1), S2.push(ns2);
    }
    return 0;
}
int main() {
    int n, d, s;
    char foo[1024];
    int i, j, k;
    while(scanf("%d %d %d", &n, &d, &s) == 3 && n+d+s) {
        while(getchar() != '\n');
        for(i = 0; i < n; i++)
            route[i].clear();
        for(i = 0; i < n; i++) {
            gets(foo);
            stringstream sin;
            sin << foo;
            int stop, si, di;
            while(sin >> stop)
                route[i].push_back(stop);
            gets(foo);
            sin.clear();
            sin << foo;
            while(sin >> si >> di) {
                driver[di][0] = si;
                driver[di][1] = i;
            }
        }
        int g[35][35] = {};
        for(i = 1; i <= d; i++) {
            for(j = i+1; j <= d; j++) {
                int encounter = sol(i, j);
                g[i][j] = g[j][i] = encounter;
            }
            g[i][i] = 1;
        }
        for(k = 1; k <= d; k++)
            for(i = 1; i <= d; i++)
                for(j = 1; j <= d; j++)
                    g[i][j] |= g[i][k]&g[k][j];
        int ret = 1;
        for(i = 1; i <= d; i++)
            for(j = 1; j <= d; j++)
                ret &= g[i][j];
        puts(ret ? "Yes" : "No");
    }
    return 0;
}