`
暴风雪
  • 浏览: 390943 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[2-sat]hdoj 4751

 
阅读更多

大致题意

给出一个有向图,问这个图是否能分为两个完全图

 

大致思路

O(n^2)建图2-sa判定t即可

#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=1000;
const int mMax=1000010;
class edge{
public:
    int v,nex;
};edge e[mMax];
int k,head[nMax];

void addedge(int a,int b){
  //  cout<<a<<"--->"<<b<<endl;
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}

int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep;   //atype 强连通分量的个数
bool insta[nMax];

void Tarjan(int u){
    int i,j;
    dfn[u]=low[u]=++dep;
    sta[++top]=u;
    insta[u]=1;
    for(i=head[u];i;i=e[i].nex){
        int v=e[i].v;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(insta[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        atype++;              //强连通分量个数
        do{
            j=sta[top--];
            belon[j]=atype;   //第j个点属于第type个连通块
            insta[j]=0;
        }while(u!=j);
    }
}

void init(){
    k=1;
    dep=1;
    top=atype=0;
    memset(insta,0,sizeof(insta)); //是否在栈中
    memset(head,0,sizeof(head));   //静态链表头指针
    memset(low,0,sizeof(low));     //Tarjan的low数组
    memset(dfn,0,sizeof(dfn));     //Tarjan的dfn数组
    memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
}

int n,mpp[103][103];
bool judge(){
    for(int i=1;i<=n;i++){
        if(belon[i]==belon[i+n]){
            return 0;
        }
    }
    return 1;
}
int main(){
    int i,j,a;
    while(cin>>n){
        init();
        memset(mpp,0,sizeof(mpp));
        for(i=1;i<=n;i++){
            while(cin>>a){
                if(a==0)break;
                mpp[i][a]=1;
            }
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if((!mpp[i][j]||!mpp[j][i])&&i!=j){
                        addedge(i,j+n);
                        addedge(i+n,j);
//                        addedge(j+n,i);
//                        addedge(j,i+n);
                }
            }
        }
        for(i=1;i<=n*2;i++){
            if(!dfn[i])Tarjan(i);
        }
        if(judge()){
            cout<<"YES\n";
        }else cout<<"NO\n";
    }
    return 0;
}


 

0
0
分享到:
评论

相关推荐

    ACM学习课件-HDOJ

    【ACM学习课件-HDOJ】是一套专门为学习算法竞赛和提高编程能力设计的教育资源。这个压缩包包含了丰富的学习材料,特别针对那些对参加ACM(国际大学生程序设计竞赛)或者提升自己的算法水平感兴趣的人。ACM竞赛是全球...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    HDOJ题目分类 HDOJ题目分类

    2. **算法类型**:包括排序(冒泡、快速、归并等)、搜索(深度优先、广度优先、二分查找等)、动态规划、贪心算法、回溯、图论(最小生成树、最短路径等)等。 3. **数据结构**:数组、链表、栈、队列、树(二叉树...

    HDOJ1003

    ACM ICPC HDOJ1003

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    HDOJ 80题 Java

    2. **数据结构**:数组、链表、栈、队列、树、图等,以及它们在实际问题中的应用。 3. **算法**:排序(冒泡、选择、插入、快速、归并等)、搜索(线性、二分、深度优先、广度优先等)、动态规划、贪心算法、回溯法...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    hdoj1002——大整数相加

    ### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ离线版

    2. **提高编程技能**:支持C、C++、Java等多种编程语言,让你有机会熟悉不同语言的编程风格和特性,同时提高编程效率和代码质量。 3. **实战训练**:题目覆盖ACM/ICPC竞赛题型,模拟比赛环境,有助于准备各类编程...

    HDOJ-from-zero-to-zero:HDOJ题解(大概。。。)

    HDOJ从零到零 &lt;&lt;&lt; &lt;&lt;&lt; &lt;&lt;&lt; &gt;&gt;&gt; &gt;&gt;&gt; &gt;&gt;&gt; :calendar:阶段性计划 :bullseye: 2021-04-30〜30题

    HDOJ 1008

    ACM ICPC HDOJ1008

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    hdoj1005 Number Sequence 代码

    ### hdoj1005 Number Sequence 代码分析与解析 #### 一、问题背景与题目概述 在深入了解代码之前,我们先来了解下题目背景。`hdoj1005 Number Sequence` 是杭州电子科技大学在线评测系统(Online Judge,简称OJ)...

    HDOJ1000

    ACM ICPC HDOJ1000

    hdoj 2013 多校训练4标程+解题报告

    2. **hdoj平台**:这是一个在线编程竞赛和练习平台,提供各种难度级别的编程题目供用户挑战,有助于提高编程技能和算法理解。 3. **解题策略**:解题报告中会涵盖如何分析问题、选择合适的数据结构和算法、以及如何...

Global site tag (gtag.js) - Google Analytics