POJ1611: The Suspects

問題

問題文

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

問題概要

n { (0 \lt n \leqq 30000) } 人の学生とその学生からなる m { (0 \leqq m \leqq 500) } 個のグループが与えられる。

全ての学生に 0 ~ n−1 の番号が振られており 0 番目の学生に SARS という病気の感染の疑いがある。感染の疑いのある学生と同じグループの学生にも感染の疑いがあるとする。

感染の疑いのある学生の人数を求めよ。

次のような入力が与えられたとき

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

1 つ目の入力は n = 100, m = 4 で

1 番目の学生は 0 番目の学生と同じグループであるから感染の疑いがあり, 1 番目の学生と同じグループである 2番目の学生, その 2 番目の学生と同じグループである 99 番目の学生も感染の疑いがあるので答えは 4 となる。

同様に 2 つ目の入力の答えは 1, 3 つ目も 1 となるので

4
1
1

が出力すべき答えである。

解答例

指針

  • 頂点 0 が属する連結成分のサイズを求める。

解説

学生のグループを連結グラフとみなすと求めるものは頂点 0 が属する連結成分のサイズとなる。

グラフの連結判定は DFS や BFS などの単純な探索をすることで O(|V| + |E|) で可能である。

Union-Find というデータ構造を用いて解くこともできる。

DFS による解法

以下のような入力に対して

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2

次のようなグラフを考える。

f:id:kira000:20180113185623p:plain

連結性のみの興味があるのでグループに属する最初の学生とそれ以外の学生を辺でつなげばいい。(他にもつなぎ方は色々ある)

頂点 0 から DFS を行い連結成分のサイズを求める。

/* Memory: 1304K
   Time: 79MS
   Language:C++ */

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

vector<int> G[30001];

bool visited[30001];
int ans;

void dfs(int v){
    visited[v] = true;
    ans++;
    for (int i = 0; i < G[v].size(); i++) {
        if (!visited[G[v][i]]) { dfs(G[v][i]); }
    }
}

int main() {
    int n, m, k;
    int leader, user;

    while (scanf("%d %d", &n, &m)) {
        if (!n && !m) { break; }

        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < n; i++) { G[i].clear(); }

        for (int i = 0; i < m; i++) {
            scanf("%d %d", &k, &leader);
            while (--k) {
                scanf("%d", &user);
                G[leader].push_back(user);
                G[user].push_back(leader);
            }
        }
        ans = 0;
        dfs(0);
        printf("%d\n", ans);
    }
}
  • 明示的に Stack を使った版

このコードの Stack を Queue に変えるだけで BFS になる。

/* Memory: 1348K
   Time: 94MS
   Language:C++ */

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

vector<int> G[30001];

bool visited[30001];
int ans;

void dfs(int v) {
    ans = 0;
    stack<int> St;
    St.push(v);
    visited[v] = true;
    while (!St.empty()) {
        int cur = St.top(); St.pop();
        ans++;
        for (int i = 0; i < G[cur].size(); i++) {
            if (!visited[G[cur][i]]) {
                St.push(G[cur][i]);
                visited[G[cur][i]] = true;
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    int n, m, k;
    int leader, user;

    while (scanf("%d %d", &n, &m)) {
        if (!n && !m) { break; }

        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < n; i++) { G[i].clear(); }

        for (int i = 0; i < m; i++) {
            scanf("%d %d", &k, &leader);
            while(--k) {
                scanf("%d", &user);
                G[leader].push_back(user);
                G[user].push_back(leader);
            }
        }
        dfs(0);
    }
    return 0;
}

DFS による解法 (二部グラフ)

各グループも頂点とみなした二部グラフを考える。

各グループを 30001 ~ 30501 までの番号をつける。

すなわち以下のような入力に対して

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2

次のような二部グラフを考える。

f:id:kira000:20180113185716p:plain

頂点 0 から DFS をして 訪れた頂点が 30000 以下のときのみをカウントして答えを求める。

/* Memory: 1312K
   Time: 94MS
   Language:C++ */

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

vector<int> G[30502];

bool visited[30502];
int ans;

void dfs(int v){
    visited[v] = true;
    if (v < 30001) { ans++; }
    for (int i = 0; i < G[v].size(); i++) {
        if (!visited[G[v][i]]) { dfs(G[v][i]); }
    }
}

int main() {
    int n, m, k, v;

    while (scanf("%d %d", &n, &m)) {
        if (!n && !m) { break; }

        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < 30502; i++) { G[i].clear(); }

        for (int i = 0; i < m; i++) {
            scanf("%d", &k);
            while (k--) {
                scanf("%d", &v);
                G[i + 30001].push_back(v);
                G[v].push_back(i + 30001);
            }
        }
        ans = 0;
        dfs(0);
        printf("%d\n", ans);
    }
    return 0;
}

Union-Find による解法

Union-Find とは互いに素な集合に対して以下の 2 つの操作を効率よく行うことが出来るデータ構造である。

  • Union : 2 つの集合を 1 つに統合する。

  • Find : 特定の要素がどの集合に属しているか見つける。

Union-Find を使うと実装が楽になる。

/* Memory: 432K
   Time: 16MS
   Language: C++ */

#include <cstdio>
#include <vector>

using namespace std;

struct uf_find_tree {
    vector<int> par, sizes;
    uf_find_tree(int n) : par(n), sizes(n, 1) {
        for (int i = 0; i < n; i++) { par[i] = i; }
    }
    int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sizes[x] < sizes[y]) { swap(x, y); }
        par[y] = x;
        sizes[x] += sizes[y];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sizes[find(x)]; }
};

int main() {
    int n, m, k, leader, user;

    while (scanf("%d %d", &n, &m)) {
        if (!n && !m) { break; }
    
        uf_find_tree uf(n);

        for (int i = 0; i < m; i++) {
            scanf("%d %d", &k, &leader);
            while (--k) {
                scanf("%d", &user);
                uf.unite(leader, user);
            }
        }
        printf("%d\n", uf.size(0));
    }
    return 0;
}

参考文献