你知道八卦嗎?
八卦是中國古代的基本哲學概念,來源有二:
一是中國古代的陰陽學說,所謂「無極生有極,有極是太極,太極生兩儀(即陰陽),兩儀生四象(即少陽,太陽,少陰,太陰),四象演八卦,八八六十四卦」,此為伏羲八卦,也叫先天八卦;
一是周文王的乾坤學說,他認為先有天地,天地相交而生成萬物,天即乾,地即坤,八卦其餘六卦皆為其子女:震為長男,坎為中男,艮為少男;巽為長女,離為中女,兌為少女,是為文王八卦,又稱後天八卦。
八卦符號通常與太極圖搭配出現,代表中國傳統信仰(儒,道)的終極真理——「道」。
「八卦」一詞在現代流行語中,特別是在娛樂新聞中被用作於謠言、緋聞等小道消息代稱。既可做名詞(如「一則八卦」),也可做形容詞(如「八卦消息」、「八卦新聞」)甚至動詞(如「八卦一下某人」,意思即談論某人的小道消息)。
而八卦的新用據說源自於香港。當時有一小道消息雜誌為了提升銷量,而仿效英國成人雜誌在刊物中加入裸女圖片,但又顧慮當時社會風氣可能無法接受,故以八卦圖代替馬賽克遮掩圖中的重點部位。
之後,八卦雜誌遂成為該類雜誌的代稱,而「八卦」一詞也增添了新意涵。
而在這個人人八卦的時代,你發明了一個八卦傳播系統,可以強制把一些八卦灌輸到一個人的腦海中。
基於每個人愛八卦的特性,有些人會將所知的八卦告訴一些好朋友,而好朋友又會將八卦告訴他們的好朋友....
但是,每使用一次八卦傳播機會耗費大量的電力,在這個節能減碳的時代,你希望使用越少次越好。
本題只有一組測試資料:
第一行有兩個數字 n, m,代表這組八卦共要讓 n 個人知道,並在這 n 個人當中,有 m 條八卦傳遞路徑
(n, m <= 100,000)
接下來有 m 行,每行有兩個數字 a, b,代表當 a 知道八卦之後,就會跟 b 八卦一下。
請對於每筆資料輸出一行,每行有一個數字 k ,代表 最少要使用幾次八卦傳播系統才能人這 n 個人都知道八卦。
對於範例測資
我們只需要對 1 灌輸八卦
1 就會把八卦傳遞給 2
2 就會把八卦傳遞給 3
※2008/10/18 測資範圍更正 by peter50216,感謝 surwdkgo。
原TIOJ1451 / 建中校內培訓第二次模擬考試。
Problem Setter:hallogameboy、peter50216
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 9 |
2 | 1 | 9 |
3 | 2 | 9 |
4 | 3 | 9 |
5 | 4 | 9 |
6 | 5 | 9 |
7 | 6 | 9 |
8 | 7 | 9 |
9 | 8 | 9 |
10 | 9 | 9 |
11 | 10 | 10 |