第1行输入日志记录的数量n。
第2行到n + 1行是日志,日志由空格分隔,第一列是来源视频avid,第二列是点击视频avid,avid是[0, 100000]的整数。
程序需输出产生最多点击的视频,如果点击数相同输出avid大的视频。
5 33956 27538 79731 91415 25288 33956 33956 84925 79731 25288
79731
import java.util.Scanner; import java.util.HashMap; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); while(in.hasNext()){ // 建立tree HashMap<Integer, Integer> treeMap = new HashMap<>(); for(int i=0; i<n; i++){ int from = in.nextInt(); int to = in.nextInt(); treeMap.put(to, from); } // 回溯记录映射深度,加上本身的值 HashMap<Integer, Integer> coutMap = new HashMap<>(); for(Integer vid:treeMap.values()){ int cot = 1; while(true){ Integer upvid = treeMap.get(vid); if(upvid==null){ Integer tmpcot = coutMap.get(vid); coutMap.put(vid, tmpcot==null?cot:tmpcot+cot); break; } cot++; vid = upvid; } } // 查找最大值 int maxcot = -1; int maxvid = -1; for(Integer key:coutMap.keySet()){ int tmpcot = coutMap.get(key); if(tmpcot>maxcot){ maxcot = tmpcot; maxvid = key; } } System.out.print(maxvid); } } }
import sys n = int(sys.stdin.readline().strip("\n")) tree = {} maxadv = 0 maxcnt = 0 for i in range(n): from_avid,to_avid = map(int,sys.stdin.readline().strip("\n").split(" ")) tree[to_avid] = from_avid cnt = {} for i in tree: cnt[i] = cnt.get(i,0)+1 f = tree[i] while f!=0: cnt[f] = cnt.get(f,0)+1 f = tree.get(f,0) for i in cnt: if maxcnt<=cnt[i]: maxadv = i if maxcnt < cnt[i] else max(maxadv,i) maxcnt = cnt[i] print(maxadv)思路很简单,因为父节点唯一,可以建立父节点后,更新的时候每次更新所有父节点,最后对比一下大小即可
// 维护一个并查集,记录当前集合中的元素个数 #include <cstdio> #include <algorithm> using namespace std; const int N = 100010; int p[N], s[N]; int n; int find(int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } int main() { scanf("%d", &n); for (int i = 1; i < N; i ++) p[i] = i, s[i] = 1; int x = -1, y = 0; while (n --) { int a, b; scanf("%d%d", &a, &b); int pa = find(a), pb = find(b); p[pb] = pa, s[pa] += s[pb]; if (s[pa] > y) x = pa, y = s[pa]; else if (s[pa] == y) x = max(x, pa); } printf("%d\n", x); return 0; }
import sys n_rows = int(sys.stdin.readline().strip()) tree = {} count_list = {} # 子节点仅仅只有一个父节点,因此构建子节点->父节点的路径 for i in range(n_rows): parent, child = map(int, sys.stdin.readline().strip('\n').split(" ")) tree[child] = parent # 每一个更新子节点->根节点路径上所有节点的计数 for parent in tree: count_list[parent] = count_list.get(parent, 0) + 1 # 向上追溯父节点,没有则置为0 node = tree.get(parent, 0) while node != 0: count_list[node] = count_list.get(node, 0) + 1 node = tree.get(node, 0) # 求最大值 max_count = 0 max_id = 0 for node in count_list: if count_list[node] > max_count: max_count = count_list[node] max_id = node # 如果有多个相同的计数,选择id更大的 elif count_list[node] == max_count and node > max_id: max_id = node print(max_id)
class UnionFind(): def __init__(self, n): self.root = [i for i in range(n)] self.cnt = [1] * n self.maxCnt = 1 self.maxCntID = 0 def find(self, p): if self.root[p] != p: p = self.find(self.root[p]) return self.root[p] def union(self, a, b): rootx = self.find(a) rooty = self.find(b) if rootx != rooty: self.root[b] = rootx self.cnt[rootx] += self.cnt[rooty] if self.cnt[rootx] > self.maxCnt&nbs***bsp;(self.cnt[rootx] == self.maxCnt and rootx > self.maxCntID): self.maxCnt = self.cnt[rootx] self.maxCntID = rootx def getMax(self): return self.maxCntID n = eval(input()) uf = UnionFind(100001) for _ in range(n): a, b = map(int, input().split()) uf.union(a, b) print(uf.getMax())并查集