[PAT-A] 1158 Telefraud Detection

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 1010;
    static int k, n, m;
    static int[][] calls = new int[N][N];
    static List<Integer> suspects = new ArrayList<>();
    static int[] gang = new int[N];
    static int gangCount = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int caller = Integer.parseInt(st.nextToken());
            int receiver = Integer.parseInt(st.nextToken());
            int duration = Integer.parseInt(st.nextToken());
            calls[caller][receiver] += duration;
        }

        for (int i = 1; i <= n; i++) {
            int totalShortCalls = 0;
            int callbackCount = 0;

            for (int j = 1; j <= n; j++) {
                if (calls[i][j] > 0 && calls[i][j] <= 5) {
                    totalShortCalls++;
                    if (calls[j][i] > 0) {
                        callbackCount++;
                    }
                }
            }

            if (totalShortCalls > k && callbackCount <= totalShortCalls * 0.2) {
                suspects.add(i);
            }
        }

        if (suspects.isEmpty()) {
            System.out.println("None");
            return;
        }

        for (int suspect : suspects) {
            if (gang[suspect] == 0) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(suspect);

                while (!queue.isEmpty()) {
                    int current = queue.poll();
                    if (gang[current] == 0) {
                        gang[current] = gangCount;
                        for (int otherSuspect : suspects) {
                            if (gang[otherSuspect] == 0 &&
                                    calls[current][otherSuspect] > 0 &&
                                    calls[otherSuspect][current] > 0) {
                                queue.offer(otherSuspect);
                            }
                        }
                    }
                }
                gangCount++;
            }
        }

        for (int i = 1; i < gangCount; i++) {
            List<Integer> gangMembers = new ArrayList<>();
            for (int suspect : suspects) {
                if (gang[suspect] == i) {
                    gangMembers.add(suspect);
                }
            }

            Collections.sort(gangMembers);
            if (!gangMembers.isEmpty()) {
                for (int j = 0; j < gangMembers.size(); j++) {
                    if (j > 0) {
                        System.out.print(" ");
                    }
                    System.out.print(gangMembers.get(j));
                }
                System.out.println();
            }
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 1010;

int n, m, k;
int g[N][N];        // [1, n]
vector<int> suspects;
int gang[N], gangNum = 1;

int main() {
    scanf("%d%d%d", &k, &n, &m);

    for (int i = 0; i < m; ++i) {
        int a, b, len;
        scanf("%d%d%d", &a, &b, &len);
        g[a][b] += len;        // 累计通话时间！
    }

    for (int i = 1; i <= n; ++i) {
        int total_cnt = 0, callback_cnt = 0;
        for (int j = 1; j <= n; ++j)
            if (g[i][j] && g[i][j] <= 5) {
                total_cnt++;
                if (g[j][i]) callback_cnt++;
            }
        if (total_cnt > k && callback_cnt <= total_cnt * 0.2)
            suspects.push_back(i);
    }

    if (suspects.empty()) {
        printf("None\n");
        return 0;
    }

    for (auto i: suspects) {
        if (!gang[i]) {
            queue<int> q;
            q.push(i);

            while (!q.empty()) {
                int t = q.front();
                q.pop();

                if (!gang[t]) {
                    gang[t] = gangNum;
                    for (auto j: suspects)
                        if (!gang[j] && g[t][j] && g[j][t])
                            q.push(j);
                }
            }
        }
        gangNum++;
    }

    for (int num = 1; num < gangNum; ++num) {
        vector<int> v;
        for (int i = 0; i < suspects.size(); ++i)
            if (gang[suspects[i]] == num)
                v.push_back(suspects[i]);

        sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); ++i) {
            if (i > 0) printf(" ");
            printf("%d", v[i]);
        }
        if (!v.empty()) printf("\n");
    }

    return 0;
}