Skip to content

1008 Airline Routes

Statement

Metadata

  • 作者: CHEN, Yue
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

Given a map of airline routes, you are supposed to check if a round trip can be planned between any pair of cities.

Input Specification

Each input file contains one test case. For each case, the first line gives two positive integers N (2\le N \le 10^4) and M (\le 6N), which are the total number of cities (hence the cities are numbered from 1 to N) and the number of airline routes, respectively. Then M lines follow, each gives the information of a route in the format of the source city index first, and then the destination city index, separated by a space. It is guaranteed that the source is never the same as the destination.

After the map information, another positive integer K is given, which is the number of queries. Then K lines of queries follow, each contains a pair of distinct cities' indices.

Output Specification

For each query, output in a line Yes if a round trip is possible, or No if not.

Sample Input 

12 19
3 4
1 3
12 11
5 9
6 2
3 2
10 7
9 1
7 12
2 4
9 5
2 6
12 4
11 10
4 8
8 12
11 8
12 7
1 5
20
11 4
12 7
3 6
2 3
5 3
3 9
4 3
8 3
8 10
10 11
7 8
7 1
9 5
1 9
2 6
3 1
3 12
7 3
6 9
6 8

Sample Output 

Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
No

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, q;

// G 原图 T 逆图
struct Graph {
    struct E {
        int to, nx, w;
    } e[N << 1];
    int h[N], cntSCC;
    void init(int n) {
        for (int i = 0; i <= n; ++i) h[i] = -1;
        cntSCC = -1;
    }
    void addedge(int u, int v, int w = 0) {
        e[++cntSCC] = {v, h[u], w};
        h[u] = cntSCC;
    }
} G, T;

struct UFS {
    int fa[N], rk[N];
    void init(int n) {
        memset(fa, 0, sizeof(fa[0]) * (n + 5));
        memset(rk, 0, sizeof(rk[0]) * (n + 5));
    }
    int find(int x) {
        return fa[x] == 0 ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (rk[fx] > rk[fy])
                swap(fx, fy);
            fa[fx] = fy;
            if (rk[fx] == rk[fy])
                ++rk[fy];
            return true;
        }
        return false;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
} ufs;

struct Kosaraju {
    bool mark[2][N];
    int sta[N], setNum[N], Belong[N], cntSCC, dOut[N];
    // setNum[i] 第i个SCC的点数
    // Belong[i] 点i属于哪个SCC
    void dfs(int u) {
        mark[0][u] = 1;
        for (int i = G.h[u]; ~i; i = G.e[i].nx) {
            int v = G.e[i].to;
            if (!mark[0][v])
                dfs(v);
        }
        sta[++*sta] = u;
    }
    void dfs1(int u) {
        mark[1][u] = 1;
        ++setNum[cntSCC];
        Belong[u] = cntSCC;
        for (int i = T.h[u]; ~i; i = T.e[i].nx) {
            int v = T.e[i].to;
            if (!mark[1][v])
                dfs1(v);
        }
    }
    void work(int n) {
        memset(mark[0], 0, sizeof(mark[0][0]) * (n + 5));
        memset(mark[1], 0, sizeof(mark[1][0]) * (n + 5));
        memset(setNum, 0, sizeof(setNum[0]) * (n + 5));
        *sta = 0;
        cntSCC = 0;
        for (int i = 1; i <= n; ++i)
            if (!mark[0][i])
                dfs(i);
        for (int i = *sta; i >= 1; --i) {
            if (!mark[1][sta[i]]) {
                ++cntSCC;
                dfs1(sta[i]);
            }
        }
    }
    void gao(int n) {
        work(n);
        scanf("%d", &q);
        for (int i = 1, u, v; i <= q; ++i) {
            scanf("%d%d", &u, &v);
            puts(Belong[u] == Belong[v] ? "Yes" : "No");
        }
    }
} kosaraju;

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        G.init(n);
        T.init(n);
        for (int i = 1, u, v; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            G.addedge(u, v);
            T.addedge(v, u);
        }
        kosaraju.gao(n);
    }
    return 0;
}
Last update: May 4, 2022
Back to top