poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)

poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

意甲冠军:给定一个有向图有m单向边缘。免费推断是否两点起来(a可以b要么b可以a或最多彼此),该请求

            弱联通重量。

算法:

缩点求强连通分量。然后又一次建图。推断新图是否是一条单链,即不能分叉,假设分叉了就会存在不可达的情况。

怎么推断是否是单链呢?

就是每次入度为0的点都仅仅有一个,即每次队列里仅仅有一个点。

poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)(    o(╯□╰)o。。。。

。好像已经是第二次用pair记录原图的点对,然后存pair的vector忘记清空导致wa来wa去!

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 1010
#define maxm 20010

using namespace std;

struct node
{
    int to,next;
}edge[maxm],edge2[maxm];
int head[maxn],cnt,n;
int clk,top,s[maxn],scc,dfn[maxn],low[maxn],belong[maxn];
bool instack[maxn],vis[maxn];
int head2[maxn],cnt2,in[maxn];

typedef pair<int,int> PII;
vector<PII> xx;
queue<int> q;

void add(int x,int y)
{
    edge[cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt++;
}

void add2(int x,int y)
{
    edge2[cnt2].to = y;
    edge2[cnt2].next = head2[x];
    head2[x] = cnt2++;
}

void dfs(int x)
{
    dfn[x] = low[x] = clk++;
    s[top++] = x;
    instack[x] = true;
    for(int i=head[x];i!=-1;i = edge[i].next)
    {
        int u = edge[i].to;
        if(dfn[u]==-1)
        {
            dfs(u);
            low[x] = min(low[u],low[x]);
        }
        else if(instack[u])
        {
            low[x] = min(low[x],dfn[u]);
        }
    }
    if(low[x]==dfn[x])
    {
        int u;
        scc++;
        do
        {
            u = s[--top];
            instack[u]=false;
            belong[u] = scc;
        }while(u!=x);
    }
}

void tarjan()
{
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    memset(belong,0,sizeof(belong));
    clk = top = scc = 0;
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==-1)
            dfs(i);
    }
}

bool topo()
{
    memset(vis,0,sizeof(vis));
    int c = 0;
    while(!q.empty())
        q.pop();
    for(int i=1;i<=scc;i++)
    {
        if(!in[i])
        {
            c++;
            q.push(i);
        }
    }
    if(c>1) return false;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        c = 0;
        for(int i=head2[u];i!=-1;i=edge2[i].next)
        {
            int v = edge2[i].to;
            in[v]--;
            if(!in[v])
            {
                q.push(v);
                c++;
            }
        }
        if(c>1)
            return false;
    }
    return true;
}

int main()
{
    int m,a,b,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        xx.clear();
        cnt = 0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            xx.push_back(make_pair(a,b));
        }
        tarjan();
        memset(head2,-1,sizeof(head2));
        cnt2 = 0;
        for(int i=0;i<xx.size();i++)
        {
            int u = xx[i].first,v = xx[i].second;
            if(belong[u]!=belong[v])
            {
                add2(belong[u],belong[v]);
                in[belong[v]]++;
            }
        }
        if(topo()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117526.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Maven 配置环境变量后无法立刻生效「建议收藏」

    Maven 配置环境变量后无法立刻生效「建议收藏」    最近在系统学习Maven,在解压完Maven,并配置环境变量后,在黑窗口用mvn-n查询不到。   仔细研究后发现,我在配置环境变量之前就打开了黑窗口,导致无法查到最新的,所以只要重新打开黑窗口就能查到了。…

  • Snapde和常用的CSV文件编辑器对比

    Snapde和常用的CSV文件编辑器对比Snapde,一个专门为编辑超大型数据量CSV文件而设计的单机版电子表格软件;它运行的速度非常快,反应非常灵敏。CSV是一种用逗号分隔列、回车分割行的文本文件,市面上常用的CSV编辑软件有:Snapde、Ron’sEditor、CSVEditorPro、DMcsvEditor、CSVPad、CSVed、CSVFileView、KillinkCSVEditor、CSVBuddy、Me…

  • linux访问服务器端口号命令_ssh的端口号

    linux访问服务器端口号命令_ssh的端口号来源:http://blog.csdn.net/u013943420/article/details/65938696大家在学习计算机的时候,对于最常用的几个端口比如80端口肯定有很深的印象,但是对于其他一些不是那么常用的端口可能就没那么了解。所以,在一些使用频率相对较高的端口上,很容易会引发一些由于陌生而出现的错误,或者被黑客利用某些端口进行入侵。对于这件事情,大部分人都很头疼——……

  • YUV和RGB的相互转换实验

    YUV和RGB的相互转换实验1、彩色空间转换基本原理1)彩色空间转换公式:为了实现格式转换,我们首先要明确待转换格式和目标格式的特点和相互转换关系,这是编程实现转换的核心。对于RGB转YUV的过程,我们要首先拿到RGB文件的数据,再通过上图的YUV计算公式对其做运算,得到YUV数据,从而实现转换。而对于YUV转RGB则要首先获得YUV数据,用第二组RGB公式计算得到RGB数据。在本实验中,转换公式如下。…

  • Php面试问题_php面试常问面试题

    Php面试问题_php面试常问面试题1、css的定位有哪些方式?以及用法position在英文中表示“位置”的意思 它主要是用于实现对元素的定位在CSS中定位分为三种:position:fixed         固定定位position:relatvie      相对定位position:absolute      绝对定位position:static      无特殊定位 (默认值)。注意:   在使用定位属…

  • 【CEGUI】资源加载流程「建议收藏」

    【CEGUI】资源加载流程「建议收藏」CEGUI资源加载流程主要资源类型Schemescheme资源(包括图像集、字体资源、窗口外观信息、类型映射)等。可以通过“.scheme“”将CEGUI系统所需要的全部资源一次加载。例:TaharezLook.scheme<?xmlversion=”1.0″?> <GUISchemeversion=”5″name=”TaharezLook”> <Imagesetfilename=”TaharezLook.imagese

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号