正題

洛谷題目
就是給出一個圖，求最小聯(lián)通塊數(shù)。

---

輸入輸出（需要自取）

Input

先是一個數(shù)N，接下來N行，分別表示各個營員愿意把自己獲得的資料拷貝給其他哪些營員。即輸入數(shù)據(jù)的第N+1行表示第i個營員愿意把資料拷貝給那些營員編號，以一個0結(jié)束。如果一個營員不愿意拷貝資料給任何人，則相應(yīng)的行只有1個0，一行中的若干數(shù)之間用一個空格隔開。

Output

一個正整數(shù)，表示最少要刻錄的光盤數(shù)。

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

1

---

解題思路

先用Floyd求每個點之間是否聯(lián)通，然后用一個f記錄他們所屬的聯(lián)通塊。

---

代碼

#include<cstdio> #include<cstring> using namespace std; int n,s,f[201]; bool a[201][201]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++){while (true){int x;scanf("%d",&x);if (x==0) break;a[i][x]=true;}}for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[i][k] && a[k][j]) a[i][j]=true;//求圖的聯(lián)通問題for (int i=1;i<=n;i++) f[i]=i;//初始化所屬聯(lián)通塊for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[i][j]) f[j]=f[i];//改變所屬聯(lián)通塊for (int i=1;i<=n;i++) if (f[i]==i) s++;//記錄聯(lián)通塊數(shù)printf("%d",s); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的ssl2344P2835-刻录光盘【Floyd,联通块数,图论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。