首页 > 其他分享 >AcWing.1175 最大半连通子图

AcWing.1175 最大半连通子图

时间:2023-01-05 20:35:03浏览次数:48  
标签:连通 int qquad 子图 stk low AcWing.1175

题目描述

\(\qquad\)一个有向图 \(G = (V,E)\) 称为半连通的,如果满足:\(\forall u,v \in V\),满足 \(u \to v\) 或 \(v \to u\),即对于图中任意两点 \(u,v\),存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。

\(\qquad\)若 \(G’ = (V’,E’)\) 满足,\(E’\) 是 \(E\) 中所有和 \(V’\) 有关的边,则称 \(G’\) 是 \(G\) 的一个导出子图。

\(\qquad\)若 \(G’\) 是 \(G\) 的导出子图,且 \(G’\) 半连通,则称 \(G’\) 为 \(G\) 的半连通子图。

\(\qquad\)若 \(G’\) 是 \(G\) 所有半连通子图中包含节点数最多的,则称 \(G’\) 是 \(G\) 的最大半连通子图。

\(\qquad\)给定一个有向图 \(G\),请求出 \(G\) 的最大半连通子图拥有的节点数 \(K\),以及不同的最大半连通子图的数目 \(C\)。

\(\qquad\)由于 \(C\) 可能比较大,仅要求输出 \(C\) 对 \(X\) 的余数。

解题思路

\(\qquad\)还是先从拓扑图\(DAG\)的角度来思考,毕竟不是\(DAG\)我们也可以用Tarjan把它缩点成\(DAG\)。
\(\qquad\)在一张图上,一个强连通分量必定是半连通子图,一条链上的若干个强连通分量,也必定可以构成半连通子图,为什么?假设是这样一个串

\[A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow A_4\Rightarrow A_5\Rightarrow A_6 \]

从\(A_1\)到\(A_2\)是必定存在一条有某个分界点\(u\in A_1\)和另一个点\(v\in A_2\)之间有一条边,只要这样我们就可以保证\(A_1和A_2\)可以构成半连通子图(因为强连通分量内每个点都是“有关系的”)

\[因而可以推出$A_2和A_3$也可以构成半连通子图,因此整条链都可以构成半连通子图。 \]

\(\qquad\qquad\)所以我们这道题尽量跑长一点的链,这样我们最后构成的半连通子图才会尽量大

\(\qquad\)因为已经是拓扑图,我们就可以通过拓扑序\(DP\),这样就可以很容易地得到它的最长链,顺便也可以统计出方案数,通过加法原理就可以得到下列方程

\[\begin{array}c 1.当f[k]=0,也就是没有被更新过的时候 \\f[k] = sz[k]\\ g[k]=1\\ 2.当f[k] < f[i] + sz[k] (发现更长的链可以更新) \\f[k] = f[i] + sz[k]\\ g[k] = g[i] (所有从走到i的,再从i走到k是唯一的)\\ 3.当f[k]=f[i]+sz[k] (发现一样长的链一起选) \\g[k] += g[i] (顺便取模) \end{array} \]

这边我们半连通子图的大小应该是

\[整条链上所有的强连通分量内点的个数和 \]

然后跑最长链,就行了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 1e5 + 10, M = 2e6 + 10;
int h[N], hs[N], e[M], ne[M], idx;
int stk[N], top, in_stk[N];
int dfn[N], low[N], stmp, scc_cnt;
int f[N], g[N], maxf, sum, id[N];
int n, m, mod, sz[N];

void add(int *h, int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u) 
{
    dfn[u] = low[u] = ++ stmp;
    stk[ ++ top] = u, in_stk[u] = true ;
    
    for (int i = h[u]; ~i; i = ne[i]) 
    {
        int j = e[i];
        if (!dfn[j]) 
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    
    if (dfn[u] == low[u]) 
    {
        int y; ++ scc_cnt;
        do 
        {
            y = stk[top -- ];
            in_stk[y] = false ;
            id[y] = scc_cnt;
            sz[scc_cnt] ++ ;
        } while (y != u);
    }
}

int main() 
{
    scanf("%d%d%d", &n, &m, &mod);
    
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    
    while (m -- ) 
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(h, u, v);
    }
    
    for (int i = 1; i <= n; i ++ ) 
        if (!dfn[i]) tarjan(i);
        
    unordered_set<long long> mp;
    
    for (int i = 1; i <= n; i ++ ) 
    {
        for (int j = h[i]; ~j; j = ne[j]) 
        {
            int k = e[j], a = id[i], b = id[k];
            if (a != b && !mp.count(a * 1e6 + b)) 
            {
                add(hs, a, b);
                mp.insert(a * 1e6 + b);
            }
        }
    }
    
    for (int i = scc_cnt; i; i -- ) 
    {
        if (!f[i]) 
        {
            f[i] = sz[i];
            g[i] = 1;
        }
        for (int j = hs[i]; ~j; j = ne[j]) 
        {
            int k = e[j];
            if (f[k] < f[i] + sz[k]) 
            {
                f[k] = f[i] + sz[k];
                g[k] = g[i];
            }
            else if (f[k] == f[i] + sz[k]) 
            {
                g[k] += g[i];
                if (g[k] >= mod) g[k] -= mod;
            }
        }
    }
    
    for (int i = scc_cnt; i; i -- ) 
    {
        if (f[i] > maxf) 
            maxf = f[i], sum = g[i];
        else if (f[i] == maxf)
        {
            sum += g[i];
            if (sum >= mod) sum -= mod;
        }
    }
    
    printf("%d\n%d\n", maxf, sum);
    
    return 0;
}

标签:连通,int,qquad,子图,stk,low,AcWing.1175
From: https://www.cnblogs.com/StkOvflow/p/17028786.html

相关文章

  • 图的连通性
    图的连通性\(\text{ByDaiRuiChen007}\)一、割点与桥割点和桥-OIWikiI.定义在一张无向图\(\mathbfG\)上,如果删除某一条无向边\((u,v)\)会使得图中的极大连......
  • 检测TCP/UDP端口的连通性
    1.TCP端口的连通性TCP端口的连通性,一般通过telnet检测,命令格式如下:telnet<targetHost><targetPort>如果出现以下内容,则表示TCP端口连通性是OK的:[root@localhost~......
  • VTK_Learning_图形基本操作进阶_连通区域分析
    1.连通区域分析许多图形数据中,并非只包含一个对象(连通区域)。而在处理这些图形数据时,有时需要对每一个对象单独处理或者让其单独显示。比如,利用MarchingCube方法提取三维图像......
  • 使用xpath爬取对应百度贴吧下面的帖子图片
    hello,小伙伴们,上次给大家分享了如何使用python的正则匹配爬取百思不得姐的网站代码,虽然说正则匹配爬取网站的执行效率高,但是正则匹配的规则编写着实是令人头痛的一件事。今......
  • 爬虫之妹子图爬取
    宅男爬虫学习第一课! 宅男们的福利来啦~ 话不多说,直接上代码! #-*-encoding:utf-8-*-#FUNCTION:Capturebeautypictureimportrequestsfrombs4importB......
  • poj1192 最优连通子集--树形dp
    原题链接:​​http://poj.org/problem?id=1192​​题意:其实就是一个求无向树的所有子树和的最大值分析:树形dpdp[i][0]表示以i为根,不包括i结点的子树获得最大权dp[i][1]表......
  • 拉普拉斯算子图像增强
    1、利用拉普拉斯算子进行图像增强本质是利用图像的二次微分对图像进行蜕化,在图像领域中微分是锐化,积分是模糊,利用二次微分对图像进行蜕化即利用邻域像素提高对比度,该算法也......
  • 搭建dg启动物理备库到nomount状态后,测试连通性时发现备库能正常连接主库,但主库却没法
    问题描述:搭建dg启动物理备库到nomount状态后,测试连通性时发现备库能正常连接主库,但主库却没法连接备库,报错ora-12528,如下所示.主库:主机名risdb+oracle11.2.0.4备库:主机......
  • 桥与割点,无向图的双连通分量
    Tarjan算法与无向图连通性Tarjan算法求割点与割边定义与性质:定义给定无向连通图\(G=(V,E)\)割点:节点\(x\inV\),若将节点\(x\)及其所相连的所有边删去之后,图\(G\)分......
  • NebulaGraph v3.3.0 发布:支持子图过滤、和大量性能优化
    NebulaGraph3.3.0支持了GETSUBGRAPH和GetNeighbors的点过滤、引入了大量性能优化,同时,开始对无tag顶点的支持默认关闭。优化优化了k-hop查询性能。#4560#47......