洛谷P1262|P2341|P2002强连通分量，缩点

作者：爱是一道菜lzb | 来源：互联网 | 2023-05-16 10:27

图论强连通分量算法，个人感觉tarjan相比两次dfs好写一点（个人看法）这三道题都在学了强连通分量算法之后都比较基础，貌似都要判断一下缩点之后每个点的入度？P1262间谍网络题意：直接复

图论强连通分量算法，个人感觉tarjan相比两次dfs好写一点（个人看法）

这三道题都在学了强连通分量算法之后都比较基础，貌似都要判断一下缩点之后每个点的入度？
P1262 间谍网络
题意：
直接复制一下数据的输入格式这里，还是比较好理解的吧
第一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。
紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间谍掌握B间谍的证据。

那么对于数对(A,B),我们可以使A指向B建图，之后tarjan算法求强连通分量缩点
tarjan算法退栈的时候，需要判断一下每一个点内部是否都有可以收买的间谍，并且求出内部的点最小的编号
最后处理一下所有的点的入度，检查入度为0的点，如果有一个点的内部没有可以收买的间谍的话直接输出它最小的编号就可以了
代码：

//Decision's template
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define DP_maxn 16
#define maxn 100000
#define INF 10000007
#define mod 1000000007
#define mst(s,k) memset(s,k,sizeof(s))

typedef long long ll;

struct Edge{
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d){}
};

/*-------------------------------template End--------------------------------*/

int n,need[maxn],p,r,ans = 0,minid[maxn];
int First[maxn],Next[maxn],Last[maxn],a[maxn],k = 0;
int dfn[maxn],low[maxn],top = 0,q[maxn],fa[maxn],sum = 0,minn[maxn],cnt = 0,s[maxn],in[maxn];
bool instack[maxn],flag[maxn];

void init()
{
    mst(First,0);
    mst(low,0);
    mst(dfn,0);
    mst(s,0);
    mst(in,0);
    for(int i = 0;i<=3000+10;i++) need[i] = INF,minid[i] = INF,minn[i] = 0;
}

void add(int x,int y)
{
    k++;
    a[k] = y;
    if(First[x]==0) First[x] = k;
    else Next[Last[x]] = k;
    Last[x] = k;
}

void tarjan(int x)
{
    cnt++;top++;
    low[x] = dfn[x] = cnt;
    q[top] = x;
    instack[x] = true;
    int t = First[x];
    while(t!=0)
    {
        int v = a[t];
        if(dfn[v]==0)
        {
            tarjan(v);
            low[x] = min(low[x],low[v]);
        }
        else if(instack[v]) low[x] = min(low[x],dfn[v]);
        t = Next[t];
    }
    if(dfn[x]==low[x])
    {
        sum++;
        while(q[top+1] != x)
        {
            int tt = q[top];
            minid[sum] =  min(minid[sum],tt);
            //cout<            if(need[tt]!=0&&need[minn[sum]]>need[tt]) {minn[sum] = tt;flag[sum] = 1;}
            //cout<            s[sum]++;
            fa[tt] = sum;
            instack[tt] = false;
            top--;
        }
    }
    //cout<}

int main()
{
    //freopen("std.in","r",stdin);
    //freopen("std.out","w",stdout);
    init();
    cin>>n>>p;
    for(int i = 1;i<=p;i++)
    {
        int id,money;
        cin>>id>>money;
        need[id] = money;
    }
    cin>>r;
    for(int i = 1;i<=r;i++)
    {
        int tmpx,tmpy;
        cin>>tmpx>>tmpy;
        add(tmpx,tmpy);
    }
    for(int i = 1;i<=n;i++)
    {
        if(dfn[i]==0) tarjan(i);
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = First[i];j;j = Next[j])
        {
            int y = a[j];
            if(fa[i]!=fa[y]) in[fa[y]]++; 
        }    
    }
    for(int i = 1;i<=sum;i++)
    {
        if(in[i]==0)
        {
            if(flag[i]==0) {cout<<"NO"<            else ans+=need[minn[i]];
        }
    }
    cout<<"YES"<    return 0;
}

P2341 [HAOI]受欢迎的牛

N个点M条有向边，给出一点的关系构建一个有向图

求强连通分量，因为在一个强连通分量内部，一个点可以到达其他的所有点，那么也就是说在里面一头牛会认为其他的牛都是受欢迎的，那么可以缩点

缩点之后，遍历一下所有的点，求出缩点之后各点的入度，出度为0的点为所求答案，ans++

代码：

//Decision's template
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define DP_maxn 16
#define maxn 100000
#define INF 10000007
#define mod 1000000007
#define mst(s,k) memset(s,k,sizeof(s))

typedef long long ll;

struct Edge{
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d){}
};

/*-------------------------------template End--------------------------------*/

int n,m,tmpx,tmpy,top = 0,k = 0,cnt = 0;
int First[maxn],Next[maxn],Last[maxn],a[maxn*2],pe[maxn],ppe[maxn];
int dfn[maxn],tmp = 0,low[maxn],q[maxn],fa[maxn];
bool instack[maxn];

void init(){
    mst(First,0);
    mst(Next,0);
    mst(a,0);
    mst(dfn,0);
    mst(low,0);
}

void add(int x,int y)
{
    k++,a[k] = y;
    if(First[x]==0) First[x] = k;
    else Next[Last[x]] = k;
    Last[x] = k;
}

void tarjan(int x)
{
    top++;cnt++;
    dfn[x] = low[x] = cnt;
    q[top] = x;
    instack[x] = true;
    int t = First[x];
    while(t!=0){
        int v = a[t];
        if(dfn[v] == 0){
            tarjan(v);
            if(low[v]        }
        else if(instack[v]&&dfn[v]         t= Next[t];
    }
    if(dfn[x] == low[x])
    {
        n++;
        while(q[top+1]!=x)
        {
            pe[n]++;
            fa[q[top]] = n;
            instack[q[top]] = false;
            top--;
        }
    }
}

int main()
{
    //freopen("std.in","r",stdin);
    //freopen("std.out","w",stdout);
    init();
    cin>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        cin>>tmpx>>tmpy;
        add(tmpx,tmpy);
    }
    m = n+1;
    for(int i = 1;i<=m-1;i++)
        if(dfn[i]==0) tarjan(i);
    for(int i = 1;i<=m-1;i++){
        for(int o = First[i];o;o = Next[o])
        if(fa[i]!=fa[a[o]]) ppe[fa[i]]++;
    }
    int pp = 0;
    for(int i = m;i<=n;i++) if(ppe[i] ==0) pp++;
    if(pp==1) cout<    else cout<<"0"<    return 0;
}

P2002 消息扩散

和上面一题差不多，就是在入度为0的点发布就可以让全部城市都得到消息

//Decision's template
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define DP_maxn 16
#define maxn 100000*6
#define INF 10000007
#define mod 1000000007
#define mst(s,k) memset(s,k,sizeof(s))

typedef long long ll;

struct Edge{
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d){}
};

/*-------------------------------template End--------------------------------*/

int n,m,tmpx,tmpy,ans = 0;
int First[maxn],Next[maxn],Last[maxn],k = 0,ru[maxn];
int q[maxn],top = 0,a[maxn],dfn[maxn],low[maxn],cnt = 0,fa[maxn],num[maxn],sum = 0;
bool instack[maxn];

void add(int x,int y)
{
    k++;
    a[k] = y;
    if(First[x]==0) First[x] = k;
    else Next[Last[x]] = k;
    Last[x] = k;
}

void tarjan(int x)
{
    top++;cnt++;
    dfn[x] = low[x] = cnt;
    q[top] = x;
    instack[x] = true;
    int t = First[x];
    while(t!=0)
    {
        int v = a[t];
        if(dfn[v]==0){
            tarjan(v);
            if(low[v]        }
        else if(instack[v]&&dfn[v]        t = Next[t];
    }
    if(dfn[x]==low[x])
    {
        sum++;
        while(q[top+1]!=x)
        {
            num[sum]++;
            fa[q[top]] = sum;
            instack[q[top]] = false;
            top--;
        }
    }
}

void init()
{
    mst(dfn,0);
    mst(low,0);
    mst(num,0);
    mst(fa,0);
}

int main()
{
    //freopen("std.in","r",stdin);
    //freopen("std.out","w",stdout);
    init();
    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        cin>>tmpx>>tmpy;
        add(tmpx,tmpy);
    }
    for(int i = 1;i<=n;i++)
    {
        if(dfn[i]==0) tarjan(i);
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = First[i];j;j = Next[j])
        {
            int v = a[j];
            if(fa[i]!=fa[v]) ru[fa[v]]++;
        }
    }
    for(int i = 1;i<=sum;i++)
    {
        if(ru[i]==0) ans++;
    }
    cout<    return 0;
}

推荐阅读

string
暑假强化训练：计算几何深度探索

经过两天的努力，终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练，不仅加深了对半平面交算法的理解，还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题，进一步巩固和拓展相关知识。 ... [详细]

蜡笔小新 2024-11-08 16:20:55
string
AOJ.863 分配书籍问题（深度优先搜索算法）

题目解析给定 n 个人和 n 种书籍，每个人都有一个包含自己喜好的书籍列表。目标是计算出满足以下条件的分配方案数量：1. 每个人都必须获得他们喜欢的书籍；2. 每本书只能分配给一个人。通过使用深度优先搜索算法，可以系统地探索所有可能的分配组合，确保每个分配方案都符合上述条件。该方法能够有效地处理这类组合优化问题，找到所有可行的解。 ... [详细]

蜡笔小新 2024-11-09 20:10:25
string
洛谷 P4035 [JSOI2008] 球形空间生成器（高斯消元法 / 模拟退火算法）

本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案，主要使用了高斯消元法和模拟退火算法。通过这两种方法，可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码，适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内，确保了算法的高效性和准确性。 ... [详细]

蜡笔小新 2024-11-08 13:55:00
string
洛谷 P1344 坏牛奶追踪问题（最小割算法应用）

在洛谷 P1344 的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。 ... [详细]

蜡笔小新 2024-11-07 14:50:22
string
2018年湘潭大学程序设计竞赛在牛客网的时间数据分析报告

本报告对2018年湘潭大学程序设计竞赛在牛客网上的时间数据进行了详细分析。通过统计参赛者在各个时间段的活跃情况，揭示了比赛期间的编程频率和时间分布特点。此外，报告还探讨了选手在准备过程中面临的挑战，如保持编程手感、学习逆向工程和PWN技术，以及熟悉Linux环境等。这些发现为未来的竞赛组织和培训提供了 valuable 的参考。 ... [详细]

蜡笔小新 2024-11-11 16:10:24
string
【BZOJ1012】[JSOI 2008] 最大数值问题：ST表优化解决方案

题目要求维护一个数列，并支持两种操作：一是查询操作，语法为QL，用于查询数列末尾L个数中的最大值；二是更新操作，用于修改数列中的某个元素。本文通过ST表（Sparse Table）优化查询效率，确保在O(1)时间内完成查询，同时保持较低的预处理时间复杂度。 ... [详细]

蜡笔小新 2024-11-09 12:14:17
string
佩尔方程的递推关系式：x² - dy² = 1 的深入解析

本文深入探讨了佩尔方程 \( x^2 - dy^2 = 1 \) 的递推关系式。通过构造特定的矩阵并利用矩阵快速幂的方法，可以高效地计算出该方程的第 k 组解。此外，文章还详细分析了递推关系式的数学背景及其在数论中的应用，为相关研究提供了坚实的理论基础。 ... [详细]

蜡笔小新 2024-11-08 11:28:27
string
寒假作业解析：第三周 2月12日第7题

尽快完成之前的练习任务！每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析：通过对比不同路线的等待时间，可以找到最优解。此问题可以通过动态规划或贪心算法来解决，具体取决于路线的复杂性和约束条件。 ... [详细]

蜡笔小新 2024-11-06 14:33:36
string
【数据结构】线段数/segment tree/interval tree

【线段树】　　本质是二叉树，每个节点表示一个区间[L,R]，设m(R-L+1)2(该处结果向下取整)左孩子区间为[L，m]，右孩子区间为[m ... [详细]

蜡笔小新 2024-11-14 23:11:47
get
iOS 多线程技术之 GCD

本文将深入探讨 iOS 中的 Grand Central Dispatch (GCD)，并介绍如何利用 GCD 进行高效多线程编程。如果你对线程的基本概念还不熟悉，建议先阅读相关基础资料。 ... [详细]

蜡笔小新 2024-11-14 15:57:40
string
2017.11.26【清华集训2017】模拟

T15483.【清华集训2017模拟11.26】简单路径T25484.【清华集训2017模拟11.26】快乐树T35485.【清华集训2017模拟11.26】字符串T1结论题，结论很 ... [详细]

蜡笔小新 2024-11-13 20:25:28
buffer
面试中如何回答“零拷贝”技术问题？

零拷贝技术是提高I/O性能的重要手段，常用于Java NIO、Netty、Kafka等框架中。本文将详细解析零拷贝技术的原理及其应用。 ... [详细]

蜡笔小新 2024-11-13 02:03:52
buffer
Halcon之图像梯度、图像边缘、USM锐化

图像梯度、图像边缘、USM锐化图像梯度、图像边缘、USM锐化图像梯度、图像边缘、USM锐化图像卷积：1.模糊2.梯度3.边缘4.锐化1.视频教程：B站、 ... [详细]

蜡笔小新 2024-11-12 21:40:43
string
如何利用Java 5 Executor框架高效构建和管理线程池

Java 5 引入了 Executor 框架，为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离，简化了多线程编程的复杂性。利用 Executor 框架，开发人员可以更灵活地控制线程的创建、分配和管理，从而提高服务器端应用的性能和响应能力。此外，该框架还提供了多种线程池实现，如固定线程池、缓存线程池和单线程池，以适应不同的应用场景和需求。 ... [详细]

蜡笔小新 2024-11-07 17:05:32
python
利用树莓派畅享落网电台音乐体验

最近重新拾起了闲置已久的树莓派，这台小巧的开发板已经沉寂了半年多。上个月闲暇时间较多，我决定将其重新启用。恰逢落网电台进行了改版，回忆起之前在树莓派论坛上看到有人用它来播放豆瓣音乐，便萌生了同样的想法。通过一番调试，终于实现了在树莓派上流畅播放落网电台音乐的功能，带来了全新的音乐享受体验。 ... [详细]

蜡笔小新 2024-11-05 09:20:37

爱是一道菜lzb

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章