1.题目

1.1 题目介绍

通过金融风控的资金流水分析，可有效识别循环转账，辅助公安挖掘洗钱组织，帮助银行预防信用卡诈骗。基于给定的资金流水，检测并输出指定约束条件的所有循环转账，结果准确，用时最短者胜。

1.2.输入

输入为包含资金流水的文本文件，每一行代表一次资金交易记录，包含本端账号ID, 对端账号ID, 转账金额，用逗号隔开。
 本端账号ID和对端账号ID为一个32位的无符号整数
 转账金额为一个32位的无符号整数
 转账记录最多为28万条
 每个账号平均转账记录数< 10
 账号A给账号B最多转账一次
举例如下，其中第一行[1,2,100]表示ID为1的账户给ID为2的账户转账100元：
1,2,100
1,3,100
2,4,90
3,4,50
4,1,95
2,5,95
5,4,90
4,6,30
6,7,29
7,4,28

1.3 输出

输出信息为一个文件，包含如下信息:
 第一行输出：满足限制条件下的循环转账个数。
说明：数据集经过处理，会保证满足条件的循环转账个数小于300万。
 第二行开始：输出所有满足限制条件的循环转账路径详情。
输出循环转账路径要按照指定排序策略进行排序：每条循环转账中，ID（ID转为无符号整数后）最小的第一个输出；总体按照循环转账路径长度升序排序；同一级别的路径长度下循环转账账号ID序列，按照字典序（ID转为无符号整数后）升序排序。
举例如下：
4
1,2,4
1,3,4
4,6,7
1,2,5,4

1.4 限制

循环转账的路径长度最小为3（包含3）最大为7（包含7），例如账户A给账户B转账，账户B给账户A转账，循环转账的路径长度为2，不满足循环转账条件。

2.题解

上面小例子来个小图解：

其实看到图之后，一切都很明了了，就是一个深度遍历，然后标志找环的问题，拿到题目第一反应就是这个，确实，这个思路可以，所以撸代码了,先撸了一个java版本的（非常原生态）：

import java.io.*;
import java.util.*;public class Main_stackFix {/*可以优化*/static HashSet<List<Integer>> hashSet = new HashSet<>();  //去重int len = 0;boolean flag = true;public void dfs(Node node, List<Integer> list, int index) { //两个用于标志的数组功能不同，一个是用于记录路径，一个是用于记录深度遍历时是否到过该点if (node == null) {flag = false;return;}//限制递归深度，防止爆栈if (list.size() >7){flag = false;return;}//如果回到原来遍历过的点，说明有环不需要再往下遍历了，把这个环作为答案记录下来if (list.contains(node.value)) {// 只要路径大于等于3，或者路径小于等于7的结果if ((list.size() - findIndex(list, node.value)) >= 3 && (list.size() - findIndex(list, node.value)) <= 7) {ArrayList<Integer> help = new ArrayList<>();for (int i = findIndex(list, node.value); i < list.size(); i++) {help.add(list.get(i));}rotate(help);hashSet.add(help);}flag = false;return;}list.add(node.value);for (int i = 0; i < node.nexts.size(); i++) {dfs(node.nexts.get(i), list, index + 1);if (flag) {list.remove(list.size() - 1);index--;flag = false;}}flag = true;return;}//通过数字找indexpublic int findIndex(List<Integer> list, Integer num) {for (int j = 0; j < list.size(); j++) {if (list.get(j).equals(num)) {return j;}}return -1;}/*======================结果处理=======================*///旋转数组中的元素public void rotate(List<Integer> list) {int min = list.get(0);for (int i = 1; i < list.size(); i++) {min = Math.min(min, list.get(i));}while (list.get(0) != min) {Integer temp = list.get(0);for (int i = 1; i < list.size(); i++) {list.set(i - 1, list.get(i));}list.set(list.size() - 1, temp);}}//格式转换public List<Integer>[] transfer(List<List<Integer>> lists){List<Integer>[] list = new List[lists.size()];for (int i = 0;i < lists.size();i++){list[i] = lists.get(i);}return list;}//字典的比较器1static class SizeComparator implements Comparator<List<Integer>> {@Overridepublic int compare(List<Integer> l1, List<Integer> l2) {if (l1.size() > l2.size()){return 1;}else {if (l1.size() == l2.size()){for (int i = 0;i < l1.size();i++){if (!l1.get(i).equals(l2.get(i))){if (l1.get(i) > l2.get(i)){return 1;}else {return -1;}}}}return -1;}}}/*=====================================读取文件=========================================*/public Integer[][] loadFile(String fileName, boolean skipTitle) {BufferedReader reader = null;try {reader = new BufferedReader(new FileReader(fileName));} catch (FileNotFoundException exception) {System.err.println(fileName + " File Not Found");return null;}List<List<Integer>> listArr = new ArrayList<>();String line = "";try {if (skipTitle) {reader.readLine();}while ((line = reader.readLine()) != null) {List<Integer> list = new ArrayList<>();String item[] = line.split(",");for (int i = 0; i < item.length; i++) {list.add(Integer.parseInt(item[i]));}listArr.add(list);}} catch (IOException exception) {System.err.println(exception.getMessage());}Integer[][] matrix = new Integer[listArr.size()][listArr.get(0).size()];for (int i = 0; i < listArr.size(); i++) {for (int j = 0; j < listArr.get(i).size(); j++) {matrix[i][j] = listArr.get(i).get(j);}}return matrix;}/*=====================================写入文件=========================================*/private void saveResult(List<Integer>[] listsAns, String predictFileName) {try {BufferedWriter out = new BufferedWriter(new FileWriter(predictFileName));System.out.println(listsAns.length);out.write(listsAns.length + "\r\n");for (int i = 0; i < listsAns.length; i++) {String str = listToString(listsAns[i], ',');out.write(str + "\r\n");}out.close();} catch (IOException exception) {System.err.println(exception.getMessage());}}//list转字符串public static String listToString(List list, char separator) {StringBuilder sb = new StringBuilder();for (int i = 0; i < list.size(); i++) {if (i == list.size() - 1) {sb.append(list.get(i));} else {sb.append(list.get(i));sb.append(separator);}}return sb.toString();}/*=================图的数据结构及操作=================*///生成图public Graph createGraph(Integer[][] matrix) {Graph graph = new Graph();for (int i = 0; i < matrix.length; i++) {Integer from = matrix[i][0];Integer to = matrix[i][1];if (!graph.nodes.containsKey(from)) {graph.nodes.put(from, new Node(from));}if (!graph.nodes.containsKey(to)) {graph.nodes.put(to, new Node(to));}Node fromNode = graph.nodes.get(from);Node toNode = graph.nodes.get(to);Edge newEdge = new Edge(fromNode, toNode);fromNode.nexts.add(toNode);fromNode.out++;toNode.in++;fromNode.edges.add(newEdge);graph.edges.add(newEdge);}return graph;}//边class Edge {public Node from;public Node to;public Edge(Node from, Node to) {this.from = from;this.to = to;}}//点class Node {public int value;public int in;public int out;public ArrayList<Node> nexts;public ArrayList<Edge> edges;public Node(int value) {this.value = value;in = 0;out = 0;nexts = new ArrayList<Node>();edges = new ArrayList<Edge>();}}//图class Graph {public HashMap<Integer, Node> nodes;public HashSet<Edge> edges;public Graph() {nodes = new HashMap<Integer, Node>();edges = new HashSet<Edge>();}}/*=====================主函数========================*/public static void main(String[] args) {/*====================测试示例数据============================*/Main_stackFix m = new Main_stackFix();Integer[][] doubles = {{1, 2, 100}, {1, 3, 100}, {2, 4, 90}, {3, 4, 50}, {4, 1, 95}, {2, 5, 95}, {5, 4, 90}, {4, 6, 30}, {6, 7, 29}, {7, 4, 28}};
//        Integer[][] doubles = {{1,2,100},{2,5,90},{5,4,95},{4,1,39}};long  createGraphStartTime = System.currentTimeMillis();Graph graph = m.createGraph(doubles);long  createGraphEndTime = System.currentTimeMillis();System.out.println("创建图的时间："  + (createGraphEndTime - createGraphStartTime));System.out.println("=========================");long  searchStartTime = System.currentTimeMillis();//遍历所有非连通图for (int k = 0; k < doubles.length; k++) {ArrayList<Integer> list = new ArrayList<>();m.dfs(graph.nodes.get(doubles[k][0]), list, 0);}long  searchEndTime = System.currentTimeMillis();System.out.println("搜索全图的时间：" + (searchEndTime - searchStartTime));long  setToListStartTime = System.currentTimeMillis();ArrayList<List<Integer>> lists = new ArrayList<>(hashSet);long  setToListEndTime = System.currentTimeMillis();System.out.println("Set转成Lists的时间：" + (setToListEndTime - setToListStartTime));long  listToArrayStartTime = System.currentTimeMillis();List<Integer>[] transferedData = m.transfer(lists);long  listToArrayEndTime = System.currentTimeMillis();System.out.println("Lists转成数组使用的时间：" + (listToArrayEndTime - listToArrayStartTime));long  listsOrderStartTime = System.currentTimeMillis();Arrays.sort(transferedData,new SizeComparator());long  listsOrderEndTime = System.currentTimeMillis();System.out.println("list排序完的时间：" + (listsOrderEndTime - listsOrderStartTime));long  saveStartTime = System.currentTimeMillis();m.saveResult(transferedData, "F:\\zhou_huaweiTest\\HWcode2020-TestData-master\\testData\\result_data.txt");long  saveEndTime = System.currentTimeMillis();System.out.println("保存数据到txt过程需要的时间" + (saveEndTime - saveStartTime));/*====================测试rotate()============================*/System.out.println("==========");List<Integer> list = new ArrayList<>();list.add(2);list.add(3);list.add(1);list.add(4);Main_stackFix m2 = new Main_stackFix();m2.rotate(list);for (Integer in:list){System.out.println(in);}}
}

上边代码也不是我最初敲的，组里的小伙伴做了，然后我接着完善了一点，算法很粗糙，没有美感，很暴力，关键是真的很耗时。。。
后边为了加快开发速度，上了python版本的，这是在参照了github上边的一个大佬的做法然后做的6+1版本：

import os
import numpy as np
import datetime# -------------------输入输出--------------------------def readData(filename):data = []f = open(filename)for line in f:line = list(map(int, line.split(',')))data.append(line)return datadef writeFile(fileName, res, t1, t2):f = open(fileName, 'w')cnt = 0for r in res:cnt += len(r)f.write(str(cnt)+'\n')for rr in res:for r in rr:for i in range(len(r)-1):f.write(t1[r[i]])f.write(t2[r[len(r)-1]])# ------------------点编号转换为连续id---------------------def convert(data):l = []d = {}for line in data:l.append(line[0])l.append(line[1])st = list(set(l))  # 其实这儿求交集更好，懒得改了st.sort()  # 排个序，输出就不用排序了for i in range(len(st)):d[st[i]] = ifor i in range(len(data)):data[i][0] = d[data[i][0]]data[i][1] = d[data[i][1]]trans1 = [str(v)+',' for v in st]trans2 = [str(v)+'\n' for v in st]return trans1, trans2, data# -------------------建立邻接表-----------------------------def createGraph(data, n):g = [[] for i in range(n)]g1 = [[] for i in range(n)]  # 反向图for line in data:g[line[0]].append(line[1])g1[line[1]].append(line[0])for i in range(n):g[i].sort()  # 排序，为了输出有序g1[i].sort()return g, g1# -------------------深度遍历找环--------------------------# 6+1思路：利用反向图标记可能成为环的倒数第一个点，再进行深度为6的搜索，搜索到被标记的点则成环。def dfs(g, k, p_o, visit, visit1, res, path):for i in range(len(g[k])):v = g[k][i]if v < p_o:  # 小于查询点p_o的点都不用访问continueif visit1[v] == -2 and visit[v] == 0:  # 当碰到倒数第一个点且这个点未被访问过，则找到一条路径path.append(v)  # 把倒数第一个点加入路径中length = len(path)if length > 2:print(f"res:.............  {res}")print(f"path:.............  {path}")res[length-3].append(path.copy())print(f"res:.............  {res}")print(f"path:.............  {path}")path.pop()if visit[v] == 1 or (visit1[v] != p_o and visit1[v] != -2):continueif len(path) == 6 or v == p_o:  # 当搜索长度到6 或者 访问到查询点p_o就不继续访问了continuevisit[v] = 1  # 访问vpath.append(v)dfs(g, v, p_o, visit, visit1, res, path)path.pop()visit[v] = 0  # 退出v点，取消访问标记# ----------------------剪枝操作-----------------------------# 3邻域剪枝思路：如果将图看作是无向图，一个点数为7的环中，距离起点最远的点距离不超过3def dfs1(g, k, p_o, visit, visit1, length):for i in range(len(g[k])):if g[k][i] < p_o or visit[g[k][i]] == 1:  # 1.小于查询点p_o的点都不用访问了;  2.当前查询中已经访问过的点不用再访问;continue# p_o为当前查找环的点，把距离p_o小于等于3的点标记为p_o(也可以标记为1，不过结束查询p_o点之后要，重新标记为-1)visit1[g[k][i]] = p_oif length == 3:continuevisit[g[k][i]] = 1dfs1(g, g[k][i], p_o, visit, visit1, length+1)visit[g[k][i]] = 0if __name__ == "__main__":start = datetime.datetime.now()# -------------------输入---------------------------data = readData('C:\\Users\\Desktop\\testData-28W\\test_data.txt')# data = readData('/data/test_data.txt')t1, t2, data = convert(data)# --------------------处理----------------------------n = len(t1)g, g1 = createGraph(data, n)visit = [0 for i in range(n)]visit1 = [-1 for i in range(n)]  # 确定3邻域path = []res = [[] for i in range(5)]  # 长度分别为3，4，5，6，7的路径for i in range(n):# --------------3邻域剪枝----------------------------------# 分别遍历g,g1确定查询点i的3邻域# 把距离小于3的点的visit1标记为i，这样就确定了3邻域(不标记为1或者0是因为每次循环不用重新初始化visit1，为了省时间)dfs1(g, i, i, visit, visit1, 1)dfs1(g1, i, i, visit, visit1, 1)# --------------深度遍历找环--------------------------------for j in range(len(g1[i])):# 将倒数第一个点（6+1）visit1标记为-2，其实可以新建一个visit2来标记的，要容易理解些。visit1[g1[i][j]] = -2path.append(i)dfs(g, i, i, visit, visit1, res, path)  # 找查询点i的所有环path.pop()for j in range(len(g1[i])):visit1[g1[i][j]] = i  # 清除visit1 "-2" 的标记# ---------------------输出-------------------------# writeFile('/projects/student/result.txt', res, t1, t2)writeFile('C:\\Users\\Desktop\\testData-28W\\result\\pyLocal\\result423-1.txt', res, t1, t2)end = datetime.datetime.now()runtime = end - startprint(f"运行时长：{runtime}")

这个速度就快多了，本地跑28W的那个数据集已经可以压缩到了32s，而线上的提交的速度29：

还是很慢，不过组里大家对py不在行，都是java的，所以换了一种语言给他们，还优化了一些小细节：

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;/*** @Date: 2020/4/22**/
public class Main {//记录顶点的数量private static List<Integer> transList;private static List<Integer>[] g1;private static List<Integer>[] g2;private static List<Integer> visited1;private static List<Integer> visited2;private static MyList<Integer> path;private static List<List<Integer>>[] res;static class MyList<T> extends ArrayList implements Cloneable {//重写Object类的clone方法@Overridepublic Object clone() {Object obj = null;//调用Object类的clone方法，返回一个Object实例obj = super.clone();return obj;}}/*** 将原始数据进行转换,并返回顶点数组*/public Integer[][] convertData(Integer[][] data) {List<Integer> list = new ArrayList<>();for (int i = 0; i < data.length; i++) {list.add(data[i][0]);list.add(data[i][1]);}//快速去重，并排好序Set<Integer> set = new HashSet<Integer>(list);List<Integer> newList = new ArrayList<>(set);Collections.sort(newList);//获得排好序的新序列，并保存transList = newList;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < newList.size(); i++) {map.put(newList.get(i), i);}//对输入数组进行转换,方便建表for (int i = 0; i < data.length; i++) {data[i][0] = map.get(data[i][0]);data[i][1] = map.get(data[i][1]);}return data;}/*** 建立邻接表，包括正向的和反向的都建立*/public void createGraph(Integer[][] data, int n) {//初始化两个要输出的表g1 = new List[n];g2 = new List[n];for (int i = 0; i < n; i++) {g1[i] = new ArrayList<>();g2[i] = new ArrayList<>();}for (Integer[] line : data) {//line：data[0] data[1] 。。。表示一行的数据g1[line[0]].add(line[1]);g2[line[1]].add(line[0]);}for (int i = 0; i < n; i++) {g1[i].sort(Comparator.comparingInt((Integer o) -> o));g2[i].sort(Comparator.comparingInt((Integer o) -> o));}}/*** 完成剪枝操作* 3邻域剪枝思路：如果将图看作是无向图，一个点数为7的环中，距离起点最远的点距离不超过3*/public void cut(List<Integer>[] graph, int k, int f_index, List<Integer> visited1, List<Integer> visited2, int length) {//1.小于查询点p_o的点都不用访问了;  2.当前查询中已经访问过的点不用再访问;for (int i = 0; i < graph[k].size(); i++) {if (graph[k].get(i) < f_index || visited1.get(graph[k].get(i)) == 1) {continue;}// f_index为当前查找环的点，把距离f_index小于等于3的点标记为f_index(也可以标记为1，不过结束查询f_index点之后要，重新标记为-1)visited2.set(graph[k].get(i), f_index);if (length == 3) {continue;}visited1.set(graph[k].get(i), 1);cut(graph, graph[k].get(i), f_index, visited1, visited2, length + 1);visited1.set(graph[k].get(i), 0);}}/*** 深度搜索找环* 6+1思路：利用反向图标记可能成为环的倒数第一个点，再进行深度为6的搜索，搜索到被标记的点则成环。*/public void deepFindCircle(List<Integer>[] graph, int k, int f_index, List<Integer> visited1, List<Integer> visited2, List<List<Integer>>[] res, MyList<Integer> path) {for (int i = 0; i < graph[k].size(); i++) {int v = graph[k].get(i);// 小于查询点p_o的点都不用访问if (v < f_index) {continue;}//当碰到倒数第一个点且这个点未被访问过，则找到一条路径if (visited2.get(v) == -2 && visited1.get(v) == 0) {//把倒数第一个点加入路径中path.add(v);int len = path.size();if (len > 2) {res[len - 3].add((List<Integer>) path.clone());}path.remove(path.size() - 1);}if (visited1.get(v) == 1 || (visited2.get(v) != f_index && visited2.get(v) != -2)) {continue;}//当搜索长度到6或者访问到查询点f_index就不继续访问了if (path.size() == 6 || v == f_index) {continue;}//访问vvisited1.set(v, 1);path.add(v);deepFindCircle(graph, v, f_index, visited1, visited2, res, path);path.remove(path.size() - 1);//退出v点，取消访问标记visited1.set(v, 0);}}/*** 读入文件方法*/public Integer[][] readFromFile(String fileName) {// 使用ArrayList来存储每行读取到的字符串ArrayList<String> arrayList = new ArrayList<>();try {File file = new File(fileName);InputStreamReader input = new InputStreamReader(new FileInputStream(file));BufferedReader bf = new BufferedReader(input);// 按行读取字符串String str;while ((str = bf.readLine()) != null) {arrayList.add(str);}bf.close();input.close();} catch (IOException e) {e.printStackTrace();}// 对ArrayList中存储的字符串进行处理int length = arrayList.size();Integer array[][] = new Integer[length][2];for (int i = 0; i < length; i++) {String s1 = arrayList.get(i).split(",")[0];String s2 = arrayList.get(i).split(",")[1];array[i][0] = Integer.parseInt(s1);array[i][1] = Integer.parseInt(s2);}// 返回数组return array;}/*** 写入文件*/public void writeToFile(List<List<Integer>>[] result, String fileName, String[] t1, String[] t2) {try {File file = new File(fileName);FileOutputStream fos = new FileOutputStream(file);BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fos));//4.准备数据，往缓冲区中写数据int sum = 0;for (List<List<Integer>> ooLine : result) {sum += ooLine.size();}//写入第一行:总数bw.write(sum + "\n");//优化！！！for (List<List<Integer>> ooLine : result){for (List<Integer> oLine : ooLine) {for (int i = 0; i < oLine.size() - 1; i++) {bw.write(t1[oLine.get(i)]);}bw.write(t2[oLine.get(oLine.size() - 1)]);}}//7.关闭流bw.close();fos.close();} catch (IOException e) {e.printStackTrace();}}public static void main(String[] args) {long start = System.currentTimeMillis();Main listMain = new Main();//读取数据  654
//        Integer[][] doubles = listMain.readFromFile("C:\\Users\\Desktop\\testData-28W\\test_data.txt");Integer[][] doubles = listMain.readFromFile("C:\\Users\\Desktop\\test_data.txt");
//        Integer[][] doubles = listMain.readFromFile("/data/test_data.txt");long end1 = System.currentTimeMillis();System.out.println("读取时间： " + (end1 - start));//转换原始数据   85Integer[][] data = listMain.convertData(doubles);long end2 = System.currentTimeMillis();System.out.println("转换数据时间： " + (end2 - end1));//建立邻接表   53int nodesNum = transList.size();listMain.createGraph(data, nodesNum);long end3 = System.currentTimeMillis();System.out.println("建立邻接表的时间： " + (end3 - end2));//初始化数据   0int[] visitArr = new int[nodesNum];int[] visit1Arr = new int[nodesNum];Arrays.fill(visit1Arr, -1);visited1 = Arrays.stream(visitArr).boxed().collect(Collectors.toList());visited2 = Arrays.stream(visit1Arr).boxed().collect(Collectors.toList());path = new MyList<>();res = new List[5];for (int i = 0; i < 5; i++) {res[i] = new ArrayList<>();}long end4 = System.currentTimeMillis();System.out.println("初始化数据时间： " + (end4 - end3));//核心算法    10681for (int i = 0; i < nodesNum; i++) {//--------------邻域剪枝----------------------------------//分别遍历g1,g2确定查询点i的3邻域//把距离小于3的点的visited2标记为i，这样就确定了3邻域(不标记为1或者0是因为每次循环不用重新初始化visited2，为了省时间)listMain.cut(g1, i, i, visited1, visited2, 1);listMain.cut(g2, i, i, visited1, visited2, 1);//--------------深度遍历找环--------------------------------for (int j = 0; j < g2[i].size(); j++) {//将倒数第一个点visited1标记为-2visited2.set(g2[i].get(j), -2);}path.add(i);//找查询点i的所有环listMain.deepFindCircle(g1, i, i, visited1, visited2, res, path);path.remove(path.size() - 1);for (int j = 0; j < g2[i].size(); j++) {//清除visited2中的 "-2" 的标记visited2.set(g2[i].get(j), i);}}long end5 = System.currentTimeMillis();System.out.println("核心算法时间： " + (end5 - end4));//写入结果前准备     12Integer[] array = transList.toArray(new Integer[nodesNum]);String[] t1 = new String[nodesNum];String[] t2 = new String[nodesNum];for (int i = 0; i < nodesNum; i++) {t1[i] = array[i] + ",";t2[i] = array[i] + "\n";}long end6 = System.currentTimeMillis();System.out.println("写入结果前准备： " + (end6 - end5));//写入文件     1181
//        listMain.writeToFile(listMain.res, "C:\\Users\\Desktop\\testData-28W\\result\\java28\\result424-1.txt", t1, t2);listMain.writeToFile(res, "C:\\Users\\Desktop\\result424-3.txt", t1, t2);
//        listMain.writeToFile(resArr,"/projects/student/result.txt");long end = System.currentTimeMillis();System.out.println("写入文件时间：" + (end - end6));//运行时间      12666System.out.println("运行时间：" + (end - start));}
}

这个自己手撸的java版本，线下跑14s，而线上提交后，大喜，线上才4.6多：

可以看出，其实核心算法选择6+1确实速度已经不错了，所以我们就决定继续沿用6+1的思路，准备改良，虽然这时候时间不多了，大概举例结束就两天吧，没办法，毕竟我们准备比赛太晚了，没准备充足，也是自己还菜。。。
队员搞一个改良版的核心算法，然后我继续将这些改成C的，就想试试换一种语言的话能不能更快，因为这次比赛华为基本也是官宣了，不适合javaer和pythoner参加的，所以，晚上加班，又改出来了一个c++版本的：

#include <bits/stdc++.h>using namespace std;#define TEST//给int起别名，int在这个工程中也可以使用ui表示了
typedef unsigned int ui;class Solution {
public:vector<vector<int>> G;vector<vector<int>> G2;unordered_map<ui, int> idHash; //sorted id to 0...nvector<ui> ids; //0...n to sorted idvector<ui> inputs; //u-v pairsvector<int> visited1;vector<int> visited2;vector<vector<vector<int>>> res;vector<int> path;int nodeCnt;int loopNum;void parseInput(string &testFile) {FILE *file = fopen(testFile.c_str(), "r");ui u, v, c;int cnt = 0;while (fscanf(file, "%u,%u,%u", &u, &v, &c) != EOF) {inputs.push_back(u);inputs.push_back(v);++cnt;}
#ifdef TESTprintf("%d Records in Total\n", cnt);
#endif}void constructGraph() {auto tmp = inputs;sort(tmp.begin(), tmp.end());tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());nodeCnt = tmp.size();ids = tmp;nodeCnt = 0;for (ui &x:tmp) {idHash[x] = nodeCnt++;}
#ifdef TESTprintf("%d Nodes in Total\n", nodeCnt);
#endifint sz = inputs.size();G = vector<vector<int>>(nodeCnt);G2 = vector<vector<int>>(nodeCnt);for (int i = 0; i < sz; i += 2) {int u = idHash[inputs[i]], v = idHash[inputs[i + 1]];G[u].push_back(v);G2[v].push_back(u);}}void dfs(vector<vector<int>> graph, int k, int f_index, vector<int> &visited1, vector<int> &visited2,vector<vector<vector<int>>> &res, vector<int> &path) {for (int i = 0; i < graph[k].size(); i++) {int v = graph[k][i];if (v < f_index) {continue;}if (visited2[v] == -2 && visited1[v] == 0) {path.push_back(v);int len = path.size();if (len > 2) {res[len - 3].push_back(path);loopNum++;}path.pop_back();}if (visited1[v] == 1 || (visited2[v] != f_index && visited2[v] != -2)) {continue;}if (path.size() == 6 || v == f_index){continue;}visited1[v] = 1;path.push_back(v);dfs(graph, v, f_index, visited1, visited2, res, path);path.pop_back();visited1[v] = 0;}}void cut(vector<vector<int>> graph, int k, int f_index, vector<int> &visited1, vector<int> &visited2, int length) {for (int i = 0; i < graph[k].size(); i++) {if (graph[k][i] < f_index || visited1[graph[k][i]] == 1) {continue;}visited2[graph[k][i]] = f_index;if (length == 3) {continue;}visited1[graph[k][i]] = 1;cut(graph, graph[k][i], f_index, visited1, visited2, length + 1);visited1[graph[k][i]] = 0;}}//search from 0...n//由于要求id最小的在前，因此搜索的全过程中不考虑比起点id更小的节点void solve() {loopNum = 0;vector<vector<vector<int>>> temp(5);res = temp;visited1 = vector<int>(nodeCnt, 0);visited2 = vector<int>(nodeCnt, -1);for (int i = 0; i < nodeCnt; i++) {if (!G[i].empty()) {//出度不为空才继续cut(G, i, i, visited1, visited2, 1);cut(G2, i, i, visited1, visited2, 1);for (int j = 0; j < G2[i].size(); j++) {visited2[G2[i][j]] = -2;}path.push_back(i);dfs(G,i,i,visited1, visited2, res, path);path.pop_back();for (int j = 0; j < G2[i].size(); j++) {visited2[G2[i][j]] = i;}}}}void save(string &outputFile) {ofstream out(outputFile);out << loopNum << endl;string t1[nodeCnt];string t2[nodeCnt];for (int i = 0; i < nodeCnt; ++i) {char temp[50] = "";sprintf(temp,"%d,",ids[i]);t1[i] = temp;sprintf(temp,"%d\n",ids[i]);t2[i] = temp;}for (auto ooLine:res) {for (auto oLine:ooLine) {for (int i = 0; i < oLine.size() - 1; ++i) {out << t1[oLine[i]];}out << t2[oLine[oLine.size() - 1]];}}}
};int main()
{
//    string testFile = "test_data2.txt";
//    string outputFile = "output.txt";
//    string testFile = "/data/test_data.txt";
//    string outputFile = "/projects/student/result.txt";string testFile = "C:\\Users\\Desktop\\testData-28W\\test_data.txt";
//    string testFile = "C:\\Users\\Desktop\\test_data.txt";string outputFile = "C:\\Users\\Desktop\\result424-27-2.txt";//#ifdef TEST
//    string answerFile = "result.txt";
//#endifauto t = clock();Solution solution;solution.parseInput(testFile);solution.constructGraph();//solution.topoSort();solution.solve();solution.save(outputFile);cout << "time:" << clock() - t << " mill" << endl;return 0;
}

由于c++用得少，已经很陌生了，很多东西都是一边敲一边百度的，所以做出来的效果可想而知，最终这个跑崩了···

哎，没准备好，大半夜的屁颠颠走去提交，满怀信心地等待，最终竟然是这个结果

今年的比赛几乎没有任何的准备，六天多的时间，也是由于疫情吧，天天都是自己一个人待在房间里拼命地撸代码，感觉人都快疯掉了，其实这种比赛除了考算法之外，对语言也有挺大的要求的，像我这种javaer真的很难深度参与进去，华为官方在一些帖子里也毫不遮掩地说java就是做开发的，不适合做算法。。。

3.总结

总结：

• 真正的算法比赛真的几乎只适合C选手参加，不过选择python写思路，或者快速开发的话，py真的不二之选，而java就是万行（十万）以上级别，方便维护的系统的首选了。
• 很多时候输入输出都要往mmap，即内存读写方面来思考，硬盘读写很慢，在比赛中不能用。
• 算法是比赛的核心，需要多次改良的，没有一蹴而就的。同一个dfs，用不同的语言，不同的数据结构（数组，list，set，map等）实现的时候速度也会明显不一样，反正就是每一个小的细节都要有足够的思考，斟酌好才行。

总的来说，这个比赛是失败的吧，前期没准备好，队友一叫就热血沸腾地兴冲冲地踏进来了，时间没把握好，和队友两人的配合也还不熟练，毕竟第一次参加比赛，平时都为公司敲码的都快忘记还有算法这事了，以后还是要狠补算法了，毕竟面试还是看算法，不说了，好好学习吧。
（就自己做个笔记，让自己记住做过了这么个比赛而已，比赛最好的成绩就是107名了，成绩不好，就不贴图了，反正最后都被推到n名之外去的了。）

4.分享

先是在这次比赛中受益颇多的某大佬（知乎上Martin）的代码，真的很容易看懂，写得很好：

#include <bits/stdc++.h>
using namespace std;#define TEST//给unsigned int起别名，unsigned int在这个工程中也可以使用ui表示了
typedef unsigned int ui;
struct Path{//ID最小的第一个输出；//总体按照循环转账路径长度升序排序；//同一级别的路径长度下循环转账账号ID序列，按照字典序（ID转为无符号整数后）升序排序int length;vector<ui> path;Path(int length, const vector<ui> &path) : length(length), path(path) {}bool operator<(const Path&rhs)const{if(length!=rhs.length) return length<rhs.length;for(int i=0;i<length;i++){if(path[i]!=rhs.path[i])return path[i]<rhs.path[i];}}
};class Solution{
public:vector<vector<int>> G;unordered_map<ui,int> idHash; //sorted id to 0...nvector<ui> ids; //0...n to sorted idvector<ui> inputs; //u-v pairsvector<int> inDegrees;vector<bool> vis;vector<Path> ans;int nodeCnt;void parseInput(string &testFile){FILE* file=fopen(testFile.c_str(),"r");ui u,v,c;int cnt=0;while(fscanf(file,"%u,%u,%u",&u,&v,&c)!=EOF){inputs.push_back(u);inputs.push_back(v);++cnt;}
#ifdef TESTprintf("%d Records in Total\n",cnt);
#endif}void constructGraph(){auto tmp=inputs;sort(tmp.begin(),tmp.end());tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());nodeCnt=tmp.size();ids=tmp;nodeCnt=0;for(ui &x:tmp){idHash[x]=nodeCnt++;}
#ifdef TESTprintf("%d Nodes in Total\n",nodeCnt);
#endifint sz=inputs.size();G=vector<vector<int>>(nodeCnt);inDegrees=vector<int>(nodeCnt,0);for(int i=0;i<sz;i+=2){int u=idHash[inputs[i]],v=idHash[inputs[i+1]];G[u].push_back(v);++inDegrees[v];}}void dfs(int head,int cur,int depth,vector<int> &path){vis[cur]=true;path.push_back(cur);for(int &v:G[cur]){if(v==head && depth>=3 && depth<=7){vector<ui> tmp;for(int &x:path)tmp.push_back(ids[x]);ans.emplace_back(Path(depth,tmp));}if(depth<7 && !vis[v] && v>head){dfs(head,v,depth+1,path);}}vis[cur]=false;path.pop_back();}//search from 0...n//由于要求id最小的在前，因此搜索的全过程中不考虑比起点id更小的节点void solve(){vis=vector<bool>(nodeCnt,false);vector<int> path;for(int i=0;i<nodeCnt;i++){if(i%100==0)cout<<i<<"/"<<nodeCnt<<endl;if(!G[i].empty()){dfs(i,i,1,path);}}sort(ans.begin(),ans.end());}void save(string &outputFile){printf("Total Loops %d\n",(int)ans.size());ofstream out(outputFile);out<<ans.size()<<endl;for(auto &x:ans){auto path=x.path;int sz=path.size();out<<path[0];for(int i=1;i<sz;i++)out<<","<<path[i];out<<endl;}}
};int main()
{
//    string testFile = "test_data2.txt";
//    string outputFile = "output.txt";
//    string testFile = "C:\\Users\\24848\\Desktop\\testData-28W\\test\\test_data.txt";string testFile = "C:\\Users\\Desktop\\test_data.txt";string outputFile = "C:\\Users\\Desktop\\result424-266666666666.txt";//#ifdef TEST
//    string answerFile = "result.txt";
//#endifauto t=clock();
//    for(int i=0;i<100;i++){Solution solution;solution.parseInput(testFile);solution.constructGraph();//solution.topoSort();solution.solve();solution.save(outputFile);cout<< "time:" << clock()-t << " 毫秒" <<endl;
//    }return 0;
}

最后大赛期间收集的资料分享一波：
华为软挑资料收集分享

没想到竟然故事的结尾还有个意外。。。已经准备不做的第二天收到消息，不小心地拿了礼品和证书，只能说这个比赛神了。。。