洛谷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;
}

推荐阅读

int
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
get
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
数组
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
input
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
const
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
java
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
list
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
const
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
const
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
const
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
const
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
数组
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
list
第四章高阶函数（参数传递、高阶函数、lambda表达式）（python进阶）的讲解和应用

本文主要讲解了第四章高阶函数（参数传递、高阶函数、lambda表达式）的相关知识，包括函数参数传递机制和赋值机制、引用传递的概念和应用、默认参数的定义和使用等内容。同时介绍了高阶函数和lambda表达式的概念，并给出了一些实例代码进行演示。对于想要进一步提升python编程能力的读者来说，本文将是一个不错的学习资料。 ... [详细]

蜡笔小新 2023-12-12 15:52:48
list
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
get
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55

爱是一道菜lzb

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

Tags | 热门标签

RankList | 热门文章