UVA247 Calling Circles 解题报告

题目链接

https://vjudge.net/problem/UVA-247

题目大意

如果两个人相互打电话（直接或间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这4个人在同一个圈里；如果e打给f但f不打给e，则不能推出e和f在同一个电话圈里。输入n（n≤25）个人的m次电话，找出所有电话圈。人名只包含字母，不超过25个字符，且不重复。

解题思路

初始输入的数据当中只知道两人是否有直接打电话，所以先用floyd求传递闭包，G[i][j]表示i是否直接或者间接给j打过电话，当且仅当G[i][j] = G[j][i] = 1时二者处于同一个电话圈，我们可以利用floyd传递闭包后的矩阵G[][]构建一个新图，仅当G[i][j] = G[j][i] = 1时连边，然后跑dfs依次输出各个联通分量。

细节请见代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define endl '\n';
const int maxn = 30;
const int INF = 0x3fffffff;
const int mod = 1e9 + 7;
map<string, int> IDCache;
vector<string> StrCache;
int G[maxn][maxn];
bool vis[maxn];
int n, m;

int getID(string s) {
    if (IDCache.count(s)) {
        return IDCache[s];
    } else {
        IDCache[s] = StrCache.size();
        StrCache.push_back(s);
        return IDCache[s];
    }
}

void floyd() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                G[i][j] |= G[i][k] && G[k][j];
}

bool isFirst = true;
void dfs(int u) {
    vis[u] = true;
    if (!isFirst)
        cout << ", ";
    cout << StrCache[u];
    isFirst = false;
    for (int v = 0; v < n; v++) {
        if (v != u && G[u][v] && !vis[v]) {
            dfs(v);
        }
    }
}

void solve() {
    int kase = 0;
    while (cin >> n >> m, n != 0) {
        StrCache.clear();
        IDCache.clear();
        memset(vis, 0, sizeof vis);
        // 输入、建立初始图
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    G[i][j] = 1;
                else
                    G[i][j] = 0;
            }
        }
        // 将名称字符串映射为整数
        while (m--) {
            string s1, s2;
            cin >> s1 >> s2;
            int u = getID(s1);
            int v = getID(s2);
            G[u][v] = 1;
        }
        // Floyd求传递闭包
        floyd();
        // 求完传递闭包后，只有G[i][j] = G[j][i] = 1时才算一个电话圈，构造一个新图，将在一个电话圈的两个人之间建立一条边，否则为0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                G[i][j] = G[i][j] && G[j][i];
                G[j][i] = G[i][j];
            }
        }
        // 在新图上输出所有的连通集
        cout << "Calling circles for data set " << ++kase << ":\n";
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                isFirst = true;
                dfs(i);
                cout << endl;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    int Case = 1;
    // cin >> Case;
    while (Case--) {
        solve();
    }  
    return 0;
}