noip201506 Message 信息傳遞

来源:http://www.cnblogs.com/543Studio/archive/2016/02/02/5178403.html
-Advertisement-
Play Games

試題描述: 有 n 個同學(編號為 1 到 n )正在玩一個信息傳遞的游戲。在游戲里每人都有一個固定的信息傳遞對象,其中,編號為 i 的同學的信息傳遞對象是編號為 T_i 的同學。游戲開始時,每人都只知道自己的生日。之後每一輪中,所有人會同時將自己當前所知的生日信息告訴各自的信息傳遞對象(註意:可能


試題描述:

有 n 個同學(編號為 1 到 n )正在玩一個信息傳遞的游戲。在游戲里每人都有一個固定的信息傳遞對象,其中,編號為 i 的同學的信息傳遞對象是編號為 T_i 的同學。游戲開始時,每人都只知道自己的生日。之後每一輪中,所有人會同時將自己當前所知的生日信息告訴各自的信息傳遞對象(註意:可能有人可以從若幹人那裡獲取信息, 但是每人只會把信息告訴一個人,即自己的信息傳遞對象)。當有人從別人口中得知自 己的生日時,游戲結束。請問該游戲一共可以進行幾輪?

輸入:

共2行,第1行包含1個正整數 n ,表示 n 個人。
第2行包含 n 個用空格隔開的正整數T_1,T_2,...,T_n ,其中第 i 個整數 T_i 表示編號為 i 的同學的信息傳遞對象是編號為 T_i 的同學, T_i <= n 且 T_i 不等於 i 。
數據保證游戲一定會結束。

輸出:

共1行,包含1個整數,表示游戲一共可以進行多少輪。

輸入示例:

5
2 4 2 3 1

輸出示例:

3

數據範圍:

n<=200000

--------------------------------------------分隔線--------------------------------------------------------

這題看了題就知道其實我們所要乾的一件事就是找最小環……(其實我考試的時候也知道是要最小環,可不知道怎麼找啊……於是乎寫了一個根本錯的東西但不知道怎麼回事還蒙了30分……學了一年C++,就差這麼一道題的70,我的省一啊……)

上面的廢話選擇性忽略好了……下麵來說這道題的重點……

找最小環的話果斷要用到強連通分量。

強連通分量:對於一個有向圖的頂點的子集S,如果在S內任取兩個頂點u和v,都能找到一條從u到v的路徑,那麼就稱S是強連通的。如果在強連通的頂點集合S中加入其他任意頂點集合後,它都不再是強連通的,那麼就稱S是原圖的一個強連通分量(SCC :Strongly Connected Component)

強連通分量的分解可以用兩次簡單的dfs來實現。

第一次dfs的時候,選取任意頂點作為起點,遍歷所有未訪問過的頂點,在回溯前給定點標號。對剩餘未訪問過的頂點不斷重覆上述過程。

完成標號後越接近圖的尾部,定點的標號越小。

第二次dfs時先將所有的邊反向,然後以標號最大的頂點為起點進行dfs,這樣可以把圖的拓撲序儲存。

代碼如下:

 1 #include<iostream>
 2 #include<cctype>
 3 using namespace std;
 4 const int MAXN=200000+10;
 5 void read(int &x){
 6     x=0;int f=1;char ch=getchar();
 7     for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 8     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
 9     x*=f;
10 }
11 //----------------------
12 int v[MAXN],first[MAXN],next[MAXN],e;
13 void AddEdge(int a,int b){
14     v[++e]=b;
15     next[e]=first[a];
16     first[a]=e;
17 }
18 
19 int vr[MAXN],firstr[MAXN],nextr[MAXN],er;
20 void AddEdger(int a,int b){
21     vr[++er]=b;
22     nextr[er]=firstr[a];
23     firstr[a]=er;
24 }
25 //----------------------
26 int n,tot,vs[MAXN],topo[MAXN];
27 bool vis[MAXN];
28 void dfs(int x){
29     vis[x]=1;
30     for(int i=first[x];i;i=next[i])
31         if(!vis[v[i]])dfs(v[i]);
32     vs[++tot]=x;
33 }
34 
35 void dfsr(int x,int k){
36     vis[x]=1;
37     topo[x]=k;
38     for(int i=firstr[x];i;i=nextr[i])
39         if(!vis[vr[i]])dfsr(vr[i],k);
40 }
41 //---------------------------
42 int cnt[MAXN];
43 int main(){
44     read(n);
45     for(int i=1;i<=n;i++){
46         int tmp;
47         read(tmp);
48         AddEdge(i,tmp);
49         AddEdger(tmp,i);
50     }
51 
52     memset(vis,0,sizeof(vis));
53     for(int i=1;i<=n;i++)
54         if(!vis[i])dfs(i);
55 
56     int k=1;
57     memset(vis,0,sizeof(vis));
58     for(int i=n;i>=1;i--)
59         if(!vis[vs[i]])dfsr(vs[i],k++);
60 
61     for(int i=1;i<=n;i++)cnt[topo[i]]++;
62     int ans=-1u>>1;
63     for(int i=1;i<=topo[vs[1]];i++){
64         if(cnt[i]!=1)ans=min(ans,cnt[i]);
65     }
66     printf("%d\n",ans);
67 }
View Code

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • java中記憶體的分配方式有兩種,一種是在堆中分配,一種是在堆棧中分配,所有new出來的對象都是在堆中分配的,函數中參數的傳遞是在棧中分配的。通常情況下堆的記憶體可以很大,比如32位操作系統中的虛擬記憶體都可以被堆所使用(當記憶體緊張的時候甚至硬碟都可以是堆的存儲空間),而堆棧的記憶體分配是有限的。 這和c+
  • Description: 求1!+2!+3!+4!+...+n!的結果。 Input: 輸入數據含有不多於50個的正整數n(1≤n≤12)。 Output: 對於每個n,輸出計算結果。每個計算結果應占獨立一行。 Sample Input: 3 6 Sample Output: 9 873 #incl
  • 本文從3個方面對Socket編程進行詳解: 一,網路編程中兩個主要的問題 二,兩類傳輸協議:TCP;UDP 三,基於Socket的java網路編程 一,網路編程中兩個主要的問題 一個是如何準確的定位網路上一臺或多台主機,另一個就是找到主機後如何可靠高效的進行數據傳輸。 在TCP/IP協議中IP層主要
  • <?xml version="1.0" encoding="UTF-8" ?> <!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd"> <m
  • <!-- MyBatis框架 --> <dependency> <groupId>org.mybatis</groupId> <artifactId>mybatis</artifactId> <version>3.2.8</version> </dependency> <!-- MySql資料庫驅動
  • 之前寫了一題費用流,竟然硬是在寫SPFA時為DIS數組賦初始值用了MEMSET數組QAQ 調試了很久也沒有弄明白自己是卡在那裡了,,,感覺被自己蠢哭了QWQ 錯誤的姿勢!! #include <cstring> #include <iostream> #include <cstdio> using
  • list是一種有序的集合,可以隨時添加和刪除其中的元素。定義有序的集合: classmates = ['Michael', 'Bob', 'Tracy'] 用len()函數可以獲得list元素的個數: len(classmates) 用索引來訪問list中每一個位置的元素,記得索引是從0開始的: c...
  • >>> print('The quick brown fox', 'jumps over', 'the lazy dog') The quick brown fox jumps over the lazy dog print()會依次列印每個字元串,遇到逗號“,”會輸出一個空格,因此,輸出的字元串是...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...