主頁 > 移動端開發 > F - 0-1 MST（求補圖的連通塊數量）

F - 0-1 MST（求補圖的連通塊數量）

2021-09-22 16:15:47 移動端開發

Powered by:NEFU AB-IN

F - 0-1 MST

  • 題意

    有一個徑訓圖，給出 n n n個點， m m m條邊權為 1 1 1的邊，其余的邊邊權為 0 0 0，問最小生成樹的權值

  • 思路

    最優的情況是盡可能的多連邊權為 0 0 0的邊，即題目沒有給出的邊，那么連好了邊權為 0 0 0的邊，就會生成多個連通塊，連通塊之間的連邊即是答案，所以答案就是補圖的連通塊數量-1

    實作的方法就是進行 d f s dfs dfs，每次進行 d f s dfs dfs找出現存頂點 u u u中不與該點相連的點，那么這些點就與 u u u在同一個連通塊內，在總集合里刪掉這些點，并且接著 d f s dfs dfs這些點

  • 代碼

    /*
 * @Author: NEFU AB-IN
 * @Date: 2021-09-21 18:43:45
 * @FilePath: \ACM\CF\2021.9.17\e.cpp
 * @LastEditTime: 2021-09-21 19:49:56
 */
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int N = 1e6 + 10;
struct Edge
{
    int v, ne;
} e[N << 2];
int h[N];
int cnt;
void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].ne = h[u];
    h[u] = cnt++;
}
void init()
{
    memset(h, -1, sizeof(h));
    cnt = 0;
}
set<int> s;

void dfs(int u)
{
    set<int> tmp = s;
    for (int i = h[u]; ~i; i = e[i].ne)
    {
        int to = e[i].v;
        tmp.erase(to);
    }
    for (auto i : tmp)
        s.erase(i);
    for (auto i : tmp)
        dfs(i);
}

signed main()
{
    IOS;
    init();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        s.insert(i);
    for (int i = 1; i <= n; ++i)
    {
        if (s.find(i) != s.end())
        {
            dfs(i);
            ans++;
        }
    }
    cout << ans - 1 << '\n';
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/302089.html

標籤：其他

上一篇：WiFi6 MTK方案初試

下一篇：“有一個產品經理的女朋友是什么體驗？”

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【從零開始擼一個App】Dagger2

    Dagger2是一個IOC框架，一般用于Android平臺，第一次接觸的朋友，一定會被搞得暈頭轉向。它延續了Java平臺Spring框架代碼碎片化，注解滿天飛的傳統。嘗試將各處代碼片段串聯起來，理清思緒，真不是件容易的事。更不用說還有各版本細微的差別。 與Spring不同的是，Spring是通過反射 ......

    uj5u.com 2020-09-10 06:57:59 more
  • Flutter Weekly Issue 66

    新聞 Flutter 季度調研結果分享 教程 Flutter+FaaS一體化任務編排的思考與設計 詳解Dart中如何通過注解生成代碼 GitHub 用對了嗎？Flutter 團隊分享如何管理大型開源專案 插件 flutter-bubble-tab-indicator A Flutter librar ......

    uj5u.com 2020-09-10 06:58:52 more
  • Proguard 常用規則

    介紹 Proguard 入口，如何查看輸出，如何使用 keep 設定入口以及使用實體，如何配置壓縮，混淆，校驗等規則。

    ......

    uj5u.com 2020-09-10 06:59:00 more
  • Android 開發技術周報 Issue#292

    新聞 Android即將獲得類AirDrop功能：可向附近設備快速分享檔案 谷歌為安卓檔案管理應用引入可安全隱藏資料的Safe Folder功能 Android TV新主界面將顯示電影、電視節目和應用推薦內容 泄露的Android檔案暗示了傳說中的谷歌Pixel 5a與折疊屏新機 谷歌發布Andro ......

    uj5u.com 2020-09-10 07:00:37 more
  • AutoFitTextureView Error inflating class

    報錯： Binary XML file line #0: Binary XML file line #0: Error inflating class xxx.AutoFitTextureView 解決： <com.example.testy2.AutoFitTextureView android: ......

    uj5u.com 2020-09-10 07:00:41 more
  • 根據Uri，Cursor沒有獲取到對應的屬性

    Android： 背景：呼叫攝像頭，拍攝視頻，指定保存的地址，但是回傳的Cursor檔案，只有名稱和大小的屬性，沒有其他諸如時長，連ID屬性都沒有 使用 cursor.getInt(cursor.getColumnIndexOrThrow(MediaStore.Video.Media.DURATIO ......

    uj5u.com 2020-09-10 07:00:44 more
  • Android連載29-持久化技術

    一、持久化技術 我們平時所使用的APP產生的資料，在記憶體中都是瞬時的，會隨著斷電、關機等丟失資料，因此android系統采用了持久化技術，用于存盤這些“瞬時”資料 持久化技術包括：檔案存盤、SharedPreference存盤以及資料庫存盤，還有更復雜的SD卡記憶體儲。 二、檔案存盤 最基本存盤方式， ......

    uj5u.com 2020-09-10 07:00:47 more
  • Android Camera2Video整合到自己專案里

    背景： Android專案里呼叫攝像頭拍攝視頻，原本使用的 MediaStore.ACTION_VIDEO_CAPTURE， 后來因專案需要，改成了camera2 1.Camera2Video 官方demo有點問題，下載后，不能直接整合到專案 問題1.多次拍攝視頻崩潰 問題2.雙擊record按鈕， ......

    uj5u.com 2020-09-10 07:00:50 more
  • Android 開發技術周報 Issue#293

    新聞 谷歌為Android TV開發者提供多種新功能 Android 11將自動填表功能整合到鍵盤輸入建議中 谷歌宣布Android Auto即將支持更多的導航和數字停車應用 谷歌Pixel 5只有XL版本 搭載驍龍765G且將比Pixel 4更便宜 [圖]Wear OS將迎來重磅更新：應用啟動時間 ......

    uj5u.com 2020-09-10 07:01:38 more
  • 海豚星空掃碼投屏 Android 接收端 SDK 集成 六步驟

    掃碼投屏，開放網路，獨占設備，不需要額外下載軟體，微信掃碼，發現設備。支持標準DLNA協議，支持倍速播放。視頻，音頻，圖片投屏。好點意思。還支持自定義基于 DLNA 擴展的操作動作。好像要收費，沒體驗。 這里簡單記錄一下集成程序。 一 跟目錄的build.gradle添加私有mevan倉庫 mave ......

    uj5u.com 2020-09-10 07:01:43 more
最新发布
  • 歡迎頁輪播影片

    如圖，引導開始，球從上落下，同時淡入文字，然后文字開始輪播，最后一頁時停止，點擊進入首頁。 在來看看效果圖。 重力球先不講，主要歡迎輪播簡單實作 首先新建一個類 TextTranslationXGuideView，用于影片展示 文本是類似的，最后會有個圖片箭頭影片，布局很簡單，就是一個 TextVi ......

    uj5u.com 2023-04-20 08:40:31 more
  • 【FAQ】關于華為推送服務因營銷訊息頻次管控導致服務通訊類訊息

    一． 問題描述 使用華為推送服務下發IM訊息時，下發訊息請求成功且code碼為80000000，但是手機總是收不到訊息； 在華為推送自助分析（Beta）平臺查看發現，訊息發送觸發了頻控。 二． 問題原因及背景 2023年1月05日起，華為推送服務對咨詢營銷類訊息做了單個設備每日推送數量上限管理，具體 ......

    uj5u.com 2023-04-20 08:40:11 more
  • 歡迎頁輪播影片

    如圖，引導開始，球從上落下，同時淡入文字，然后文字開始輪播，最后一頁時停止，點擊進入首頁。 在來看看效果圖。 重力球先不講，主要歡迎輪播簡單實作 首先新建一個類 TextTranslationXGuideView，用于影片展示 文本是類似的，最后會有個圖片箭頭影片，布局很簡單，就是一個 TextVi ......

    uj5u.com 2023-04-20 08:39:36 more
  • 【FAQ】關于華為推送服務因營銷訊息頻次管控導致服務通訊類訊息

    一． 問題描述 使用華為推送服務下發IM訊息時，下發訊息請求成功且code碼為80000000，但是手機總是收不到訊息； 在華為推送自助分析（Beta）平臺查看發現，訊息發送觸發了頻控。 二． 問題原因及背景 2023年1月05日起，華為推送服務對咨詢營銷類訊息做了單個設備每日推送數量上限管理，具體 ......

    uj5u.com 2023-04-20 08:39:13 more
  • iOS從UI記憶體地址到讀取成員變數（oc/swift）

    開發除錯時，我們發現bug時常首先是從UI顯示發現例外，下一步才會去定位UI相關連的資料的。XCode有給我們提供一系列debug工具，但是很多人可能還沒有形成一套穩定的除錯流程，因此本文嘗試解決這個問題，順便提出一個暴論：UI顯示例外問題只需要兩個步驟就能完成定位作業的80%： 定位例外 UI 組 ......

    uj5u.com 2023-04-19 09:16:23 more
  • FIDE重磅更新！性能飛躍！體驗有禮！

    FIDE 開發者工具重構升級啦！實作500%性能提升，誠邀體驗！ 一直以來不少開發者朋友在社區反饋，在使用 FIDE 工具的程序中，時常會遇到諸如加載不及時、代碼預覽/渲染性能不如意的情況，十分影響開發體驗。 作為技術團隊，我們深知一件趁手的開發工具對開發者的重要性，因此，在2023年開年，FinC ......

    uj5u.com 2023-04-19 09:16:15 more
  • 游戲內嵌社區服務開放，助力開發者提升玩家互動與留存

    華為 HMS Core 游戲內嵌社區服務提供快速訪問華為游戲中心論壇能力，支持玩家直接在游戲內瀏覽帖子和交流互動，助力開發者擴展內容生產和觸達的場景。 一、為什么要游戲內嵌社區？ 二、游戲內嵌社區的典型使用場景 1、游戲內打開論壇 您可以在游戲內繪制論壇入口，為玩家提供沉浸式發帖、瀏覽、點贊、回帖、 ......

    uj5u.com 2023-04-19 09:15:46 more
  • iOS從UI記憶體地址到讀取成員變數（oc/swift）

    開發除錯時，我們發現bug時常首先是從UI顯示發現例外，下一步才會去定位UI相關連的資料的。XCode有給我們提供一系列debug工具，但是很多人可能還沒有形成一套穩定的除錯流程，因此本文嘗試解決這個問題，順便提出一個暴論：UI顯示例外問題只需要兩個步驟就能完成定位作業的80%： 定位例外 UI 組 ......

    uj5u.com 2023-04-19 09:14:53 more
  • FIDE重磅更新！性能飛躍！體驗有禮！

    FIDE 開發者工具重構升級啦！實作500%性能提升，誠邀體驗！ 一直以來不少開發者朋友在社區反饋，在使用 FIDE 工具的程序中，時常會遇到諸如加載不及時、代碼預覽/渲染性能不如意的情況，十分影響開發體驗。 作為技術團隊，我們深知一件趁手的開發工具對開發者的重要性，因此，在2023年開年，FinC ......

    uj5u.com 2023-04-19 09:14:08 more
  • 游戲內嵌社區服務開放，助力開發者提升玩家互動與留存

    華為 HMS Core 游戲內嵌社區服務提供快速訪問華為游戲中心論壇能力，支持玩家直接在游戲內瀏覽帖子和交流互動，助力開發者擴展內容生產和觸達的場景。 一、為什么要游戲內嵌社區？ 二、游戲內嵌社區的典型使用場景 1、游戲內打開論壇 您可以在游戲內繪制論壇入口，為玩家提供沉浸式發帖、瀏覽、點贊、回帖、 ......

    uj5u.com 2023-04-19 09:08:34 more

Copyright © 2010-2020 有解無憂