資訊專欄INFORMATION COLUMN
摘要：題目描述團(tuán)隊(duì)在月日搬入了學(xué)清嘉創(chuàng)大廈，為慶祝團(tuán)隊(duì)的喬遷之喜，字節(jié)君決定邀請整個(gè)團(tuán)隊(duì)，舉辦一個(gè)大型團(tuán)建游戲字節(jié)跳動(dòng)大闖關(guān)。這個(gè)人每個(gè)人都向字節(jié)君提供了自己認(rèn)識的人的名字，不包括自己。其他所有人均刻意直接或間接的認(rèn)識，分在同一組。
題目描述
Bytedance Efficiency Engineering團(tuán)隊(duì)在8月20日搬入了學(xué)清嘉創(chuàng)大廈，為慶祝團(tuán)隊(duì)的喬遷之喜，字節(jié)君決定邀請整個(gè)EE團(tuán)隊(duì)，舉辦一個(gè)大型團(tuán)建游戲-字節(jié)跳動(dòng)大闖關(guān)?？墒怯龅搅艘粋€(gè)問題：
EE團(tuán)隊(duì)共有n個(gè)人，大家都比較害羞，不善于與陌生人交流。這n個(gè)人每個(gè)人都向字節(jié)君提供了自己認(rèn)識的人的名字，不包括自己。如果A的名單里有B，或B的名單里有A，則代表A與B相互認(rèn)識。同時(shí)，如果A認(rèn)識B，B認(rèn)識C，則代表A與C也會(huì)很快的認(rèn)識，畢竟通過B的介紹，兩個(gè)人就可以很快相互認(rèn)識的了。
為了大闖關(guān)游戲可以更好地團(tuán)隊(duì)寫作、氣氛更活躍，并使得團(tuán)隊(duì)中的人可以盡快的相互了解、認(rèn)識和交流，字節(jié)君決定根據(jù)這個(gè)名單將團(tuán)隊(duì)分為m組，每組人數(shù)可以不同，但組內(nèi)的任何一個(gè)人都與組內(nèi)的其他所有人直接或間接的認(rèn)識和交流。如何確定一個(gè)方案，使得團(tuán)隊(duì)可以分為m組，并且這個(gè)m盡可能地小呢？
輸入描述第一行一個(gè)整數(shù)n，表示有n個(gè)人，從1開始編號 接下來n行，分別表示第i個(gè)人認(rèn)識的人的編號k（1<=k<=n），每個(gè)人的名單以0代表結(jié)束輸出描述
一個(gè)整數(shù)m，代表可以聞的最小的組的個(gè)數(shù)示例
輸入
10 0 5 3 0 8 4 0 9 0 9 0 3 0 0 7 9 0 0 9 7 0
輸出
2
說明
1號同學(xué)孤獨(dú)的自己一個(gè)組，他誰也不認(rèn)識，也沒有人認(rèn)識他。其他所有人均刻意直接或間接的認(rèn)識，分在同一組。解法 思路
采用并查集。
對于圖G(V,E)，每個(gè)人為一個(gè)節(jié)點(diǎn)v，如果x號同學(xué)和y號同學(xué)認(rèn)識或者間接認(rèn)識，則(x,y)為圖中的一條邊。
set數(shù)組用來表示這個(gè)圖，最后計(jì)算圖set中有多少連通分支。
set[x]=x時(shí)，代表x為該連通分支的根節(jié)點(diǎn)，有多少根節(jié)點(diǎn)就有多少連通分支。
let n = parseInt(readline());
let arr = new Array();
let set = new Array();
for(let i = 0; i < n; i++){
let line = readline().split(" ");
arr[i] = new Array();
set[i] = i;
for(let j = 0; j < line.length; j++){
arr[i][j] = parseInt(line[j]) - 1;
}
}
for(let i = 0; i < n; i++){
for(let j = 0; j < arr[i].length-1; j++){
union(set, i, arr[j]);
}
}
let count = 0;
for(let i = 0; i < n; i++){
if(set[i] == i){
count++;
}
}
print(count);
//返回x的根節(jié)點(diǎn)
function root(set, x){
if(set[x] != x){
root(set[x]);
}else{
return x;
}
}
//合并x和y所在的兩個(gè)連通分支
function union(set, x, y){
let xroot = root(set, x);
let yroot = root(set, y);
if(xroot != yroot){
set[y] = xroot;
set[yroot] = xroot;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/97306.html
摘要：今年歲，畢業(yè)之后進(jìn)入一家小型的互聯(lián)網(wǎng)公司工作，名字就不說了，算是熟知的，在這家公司呆了兩年，直至今年才有了跳槽的想法。在眾多大廠中，最終選擇了字節(jié)跳動(dòng)。這樣的調(diào)整，一方面對自己學(xué)習(xí)有幫助，另一方面讓自己應(yīng)對面試更從容，更順利。 ...
摘要：題目描述雙生詞雙生詞是指滿足如下條件的兩個(gè)字符串假設(shè)兩個(gè)字符串分別為和字符串長度相同將字符串收尾繞成環(huán)，再選一個(gè)位置切開，順時(shí)針或逆時(shí)針能夠得到字符串容易得到，若與為雙生詞，則與也為雙生詞給定一批僅有英文小寫字母組成的字符串，詢問他們之中是 題目描述 雙生詞 雙生詞是指滿足如下條件的兩個(gè)字符串：（假設(shè)兩個(gè)字符串分別為S和S’） 1. 字符串長度相同 2. 將字符串S收尾繞成環(huán)，再選一個(gè)...
摘要：面試后面試后及時(shí)總結(jié)，有可能下一個(gè)面試官會(huì)問你同樣的問題。同時(shí)面試官也對我的未來技術(shù)發(fā)展提出了很多建議?？偟膩碚f，四面的氛圍并沒有想象得那么嚴(yán)肅，面試官也說面試得很愉快。 ...
摘要：為了避免它，只需分配將要使用的必要構(gòu)造函數(shù)。示例對于此示例，就需要保持父構(gòu)造函數(shù)繼續(xù)正常工作。結(jié)論手動(dòng)設(shè)置或更新構(gòu)造函數(shù)可能會(huì)導(dǎo)致不同且有時(shí)令人困惑的后果。為了防止它，只需在每個(gè)特定情況下定義構(gòu)造函數(shù)的角色。 hr小姐姐說一共有1輪筆試 + 3輪技術(shù)面 + 1輪hr面，面試地點(diǎn)在中關(guān)村天使大廈，崗位是1-3年前端 筆試 筆試分為多選 簡答 判斷 手寫代碼四部分，下面只寫了印象比較深的幾...
閱讀 1816·2021-11-11 11:02
閱讀 1736·2021-09-22 15:55
閱讀 2521·2021-09-22 15:18
閱讀 3522·2019-08-29 11:26
閱讀 3780·2019-08-26 13:43
閱讀 2685·2019-08-26 13:32
閱讀 934·2019-08-26 10:55
閱讀 996·2019-08-26 10:27
