首页 > 其他分享 >强连通分量习题随笔

强连通分量习题随笔

时间：2024-01-27 15:23:02浏览次数：25  
标签：连通 idx int stk ++ dfn low 习题 随笔

1.强连通分量

通过强连通分量的缩点，抢一个普通的有向图变成有向无环图

习题1 有向图缩点

给定一个 \(n\) 个点 \(m\) 条边的有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是重复经过的点，权值只计算一次。

(标明粗体的是重点)

首先允许多次经过显然就是说可以走环了，但是如果按照普通的最短路算法，走环这样的情况显然是不允许的，所以我们考虑用 \(tarjan\) 算法缩点，然后重建图，用拓扑序进行一次

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 5e5 + 10;
int h[N], e[M], ne[M], idx;
int nwh[N], nwe[M], nwne[M], nidx;
int dfn[N], low[N], timestamp;
int stk[N], top, f[N], size[N], SCC, id[N], tt[N];
bool instk[N];
int dis[N], n, m, din[N], p[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void add1(int a, int b)
{
    nwe[nidx] = b, nwne[nidx] = nwh[a], nwh[a] = nidx++;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u, instk[u] = 1;
    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 (instk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (low[u] == dfn[u])
    {
        int y = -1;
        SCC++;
        while (y = stk[top--])
        {
            tt[y] = u;
            instk[y] = 0;
            size[SCC]++;
            id[y] = SCC;
            if (y == u)
                break;
            p[u] += p[y];
        }
    }
}

int topo()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (tt[i] == i && !din[i])
            q.push(i), dis[i] = p[i];
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = nwh[t]; ~i; i = nwne[i])
        {
            int j = nwe[i];
            dis[j] = max(dis[j], dis[t] + p[j]);
            din[j]--;
            if (!din[j])
                q.push(j);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dis[i]);
    return ans;
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(nwh, -1, sizeof(nwh));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%d", &p[i]);
    for (int i = 1, x, y; i <= m; i++)
    {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i);
    }
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j])
        {
            int a = tt[i], b = tt[e[j]];
            if (a != b)
            {
                add1(a, b);
                din[b]++;
            }
        }
    cout << topo() << endl;
    return 0;
}

习题2 受欢迎的牛

每头奶牛都梦想成为牛棚里的明星，被所有奶牛喜欢的奶牛就是一头明星奶牛。每头奶牛总是喜欢自己的，奶牛之间的“喜欢”是可以传递的——如果 A 喜欢 B，B 喜欢 C，那么 A 也喜欢 C。牛栏里共有 \(n\) 头奶牛，给定一些奶牛之间的喜欢关系，请你算出有多少头奶牛可以当明星。

同样的，如果直接去看奶牛们的关系图，我们可能会想到一个暴力解——以每个点为终点，然后再看一下是不是每一个点都能到达它（ 并查集），时间复杂度 \(O(n^2)\) 显然过不了了

那我们考虑把环缩点，然后重构图，至于判断明星奶牛的数量，我们只需要遍历所有的强连通分量，通过模拟可以发现，如果新图中，出度为0的大于等于2个，就说明根本就不存在明星奶牛(因为这两个出度为0的连通分量无法互相喜欢)，否则，明星奶牛的个数就是出度为 0 的强连通分量的节点个数。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 5e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool instk[N];
int id[N], SCC, size[N];
int dout[N], zero = 0;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, instk[u] = 1;
    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 (instk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u])
    {
        int y = -1;
        ++SCC;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            id[y] = SCC;
            size[SCC]++;
        } while (y != u);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i);
    }
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
                dout[a]++;
        }
    int sum = 0;
    for (int i = 1; i <= SCC; i++)
    {
        if (!dout[i])
        {
            zero++;
            sum += size[i];
            if (zero > 1)
            {
                sum = 0;
                break;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

习题3 最大半连通子图

image-20240127145250381

所谓半连通图，就是指在半连通图中任选两点 \((u,v)\) 满足，\(u\) 能到 \(v\) 或者 \(v\) 能到 \(u\) ， 从含义可以知道，我们的强连通分量显然也是半联通的，然后我们发现，缩点建新图之后，如果强联通分量 \(SCC_1\)和\(SCC_2\) 之间有一条路线，那么显然这两个东西合到一起符合半联通子图的条件，问题就变成了信徒中寻找最长链的问题。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 100010 , M = 2000010;
int h[N],sh[N],ne[M],e[M],idx;
int stk[N],top,times;
bool in_stk[N];
int dfn[N],low[N];
int id[N],scc_cnt,Size[N];
int f[N],g[N];
int n,m,mod;
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] = ++ times ;
    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])
    {
        scc_cnt ++;
        int y;
        do{
            y = stk[top --];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;           
        }while(y != u);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&mod);
    memset(h,-1,sizeof h);
    memset(sh,-1,sizeof sh);
    while(m -- )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(h,a,b);
    }

    for(int i = 1;i <= n;i ++)
    if(!dfn[i]) tarjan(i);

    unordered_set <LL> S;
    for(int u = 1;u <= n;u ++)
    {
        for(int i = h[u]; ~i;i = ne[i])
        {
            int j = e[i];
            int a = id[u],b = id[j];
            LL hash = a * 1000000ll + b;
            if(a != b && !S.count(hash))
            {
                add(sh,a,b);
                S.insert(hash);
            }
        }
    }


    for(int i = scc_cnt; i ;i --)
    {
        if(! f[i])
        {
            f[i] = Size[i];
            g[i] = 1;
        }
        for(int j = sh[i]; ~j ; j = ne[j])
        {
            int k = e[j];
            if(f[k] < f[i] + Size[k])
            {
                f[k] = f[i] + Size[k];
                g[k] = g[i];
            }
            else if(f[k] == f[i] + Size[k]) 
                    g[k] = (g[k] + g[i]) % mod;
        }
    }

    int maxn = 0 ,sum = 0;
    for(int i = 1;i <= scc_cnt;i ++)
    if(f[i] > maxn)
    {
        maxn = f[i];
        sum = g[i];
    }
    else if(f[i] == maxn) sum = (sum + g[i]) % mod;

    printf("%d\n%d\n",maxn,sum);
    return 0;
}

习题4 网络传输

给定 \(n\) 个点 \(m\) 条边的带边权有向图，沿边方向传输信息的代价为该边的边权，特殊的，同一个强联通分量内的点间传输代价为 0，求点 \(1\) 到点 \(n\) 的最小传输代价。

简单，实际上就是缩点+最短路即可

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;                       //原图
int hs[M], es[M], nes[M], sw[M], nidx;                  //缩点后的图
int dfn[N], SCC, low[N], stk[N], top, timestamp, id[N]; //强连通分量
bool vis[N], instk[N];
int dis[N]; //最短路径
int n, m;

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

void add1(int a, int b, int c)
{
    es[nidx] = b, nes[nidx] = hs[a], sw[nidx] = c, hs[a] = nidx++;
}

void tarjan(int u) //强连通分量模板
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, instk[u] = 1;
    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 (instk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (low[u] == dfn[u])
    {
        int y = -1;
        SCC++;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            id[y] = SCC;
        } while (y != u);
    }
}

void dij() //迪杰斯特拉最短路
{
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    dis[id[1]] = 0;
    priority_queue<pair<int, int>> q;
    q.push({0, id[1]});
    while (q.size())
    {
        int t = q.top().second;
        q.pop();
        if (vis[t])
            continue;
        vis[t] = 1;
        for (int i = hs[t]; ~i; i = nes[i])
        {
            int j = es[i];
            if (dis[j] > dis[t] + sw[i])
            {
                // cout << t << ' ' << dis[t] << endl;
                dis[j] = dis[t] + sw[i];
                q.push({-dis[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(hs, -1, sizeof(hs));
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++) //建图
        for (int j = h[i]; ~j; j = ne[j])
        {
            int a = id[i], b = id[e[j]];
            if (a != b)
                add1(a, b, w[j]); //建图应该建的边权是w[j]而不是w[i]
        }
    if (id[1] == id[n])
    {
        puts("0");
        return 0;
    }
    dij();
    cout << dis[id[n]] << endl;
    return 0;
}

习题5 通讯问题

image-20240127151411556

缩完点后我们可以这样考虑，由于每一个点都会被走过，所以对于到达每一个点的最小代价，就是这个点的最小入边，毕竟题目中并不是让我们求最短路径

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = N * 3;
int h[N], e[M], ne[M], w[M], idx, n, m, ans;
int hs[N], es[M], nes[M], sw[M], nidx;
int dfn[N], low[N], timestamp, stk[N], top, id[N], SCC;
bool instk[N];
int minn[N], out[N];

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

void add1(int a, int b, int c)
{
    es[nidx] = b, nes[nidx] = hs[a], sw[nidx] = c, hs[a] = nidx++;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u, instk[u] = 1;
    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 (instk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (low[u] == dfn[u])
    {
        int y = -1;
        SCC++;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            id[y] = SCC;
        } while (y != u);
    }
}

int main()
{
    while (cin >> n >> m && !(n == 0 && m == 0))
    {
        idx = nidx = top = ans = SCC = timestamp = 0;
        memset(h, -1, sizeof(h));
        memset(hs, -1, sizeof(hs));
        memset(e, 0, sizeof(e));
        memset(es, 0, sizeof(es));
        memset(w, 0, sizeof(w));
        memset(nes, 0, sizeof(nes));
        memset(ne, 0, sizeof(ne));
        memset(minn, 0x3f, sizeof(minn));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(instk, 0, sizeof(instk));
        memset(stk, 0, sizeof(stk));
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            add(u + 1, v + 1, w);
        }
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                tarjan(i);
        for (int i = 1; i <= n; i++)
            for (int j = h[i]; ~j; j = ne[j])
            {
                int a = id[i], b = id[e[j]];
                if (a != b)
                    minn[b] = min(minn[b], w[j]);
            }
        int ans = 0;
        for (int i = 1; i <= SCC; i++)
        {
            if (i == id[1])
                continue;
            ans += minn[i];
        }
        cout << ans << endl;
    }
    return 0;
}

标签：连通,idx,int,stk,++,dfn,low,习题,随笔
From： https://www.cnblogs.com/ljfyyds/p/17991477

相关文章

  • 数论习题
    -P2568GCD给定\(n\)，求：\[\sum\limits_{p\in\mathbb{P}}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=p]\]其中\(\mathbb{P}\)为质数集。推式子：\[\begin{aligned}\sum\limits_{p\in\mathbb{P}}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[......
  • 【板子】强连通分量（SCC）
    //强连通分量//lg2863求强连通分量的数量#include<bits/stdc++.h>usingnamespacestd;constintN=(int)2e4+4;intwhere[N];//这个点在哪个scc里intscccnt;intsccsize[N];intlow[N],dfn[N],idx;boolinstk[N];stack<int>stk;vector<int>e[N];intn,m;......
  • 【随笔】2024年1月1日
    关于Febonacci的一些事学了矩阵加速递推遂顺手给你谷的板子题又过了一遍对于“已知递推式求转移矩阵”的方法仍有疑惑与巨佬WPP交流并丢给WPP一道题请他口糊题：求Febonacci前n项的和(n<=1e18)正解是把S(n)(表示前n项的和)塞到矩阵里一起转移答案矩阵F(n)={f(n-1)f(n-2)S(n......
  • 工作随笔
    导语吾日三省吾身：为人谋而不忠乎？与朋友交而不信乎？传不习乎？  记录2024-1-17：继续研究开发ai2024-1-22：怕明日的设备要还回去，先分析明日的录像存储功能。需要帮朴工找到一个ts&mp4分析工具，ai暂停2024-1-23：帮客户处理了一下onvif客户端兼容发现设备功能由于码......
  • 人工智能 第2章 课后习题
    人工智能第2章课后习题讨论题1．搜索为什么是AI系统的重要组成部分？人工智能中的搜索指依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程，是AI系统的核心内容。2．状态空间图是什么？状态空间图是对问题的一种表示......
  • 小千同学的第一篇随笔——后悔
    随笔是什么呢？不太懂的呢！那就记录一句最适合今天的句子吧！本来是这么想的，但是查查手机后突然就很想谈谈“后悔”这种情绪。后悔为什么想到这个呢？这些天我都很开心，没有内耗自己。但是在今天突然就有些郁闷，伤心，内耗了。我想这是因为我今天有了“后悔”这种情绪。后悔高三为什么......
  • 【习题】3.1
    [T030101]证明初值问题\(\frac{\mathrmdy}{\mathrmdx}=x^2+e^{-y^2},\y(0)=0\)的解\(y=\varphi(x)\)在\([0,\frac12]\)上存在,且当\(x\in[0,\frac12]\)时,\(|\varphi(x)|\le1\).    证设\(f(x,y)=x^2+e^{-y^2}\),取矩形区域\(R:\|x|\le1,\|y|\le......
  • 连通性问题
    求割点#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllN=2e4+10;lln,m,dfn[N],low[N],tot,root;boolcut[N];vector<ll>G[N];voidtarjan(llu){ dfn[u]=low[u]=++tot; llflag=0; for(autov:G[u]){ if(!dfn[v]){ ta......
  • 《数学分析习题课讲义2.1-2.2》
    ......
  • C++U5-第03课-深度优先搜索3-连通块类型
    学习目标 本节课主要学习一种类型的深度优先搜索-连通块  [数水坑]  【思路分析】相连的水坑可以被认为是一个水坑，求水坑的个数，就是求连通块的个数。可以采用搜索来访问每个点。每访问到一个W表示至少有一个水坑，通过搜索8个方向，得到这个点连通的所有的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99