大致题意
给出一个有向图,问这个图是否能分为两个完全图
大致思路
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; }
相关推荐
这些课件是杭电acm的学习课件,每个课件后面都有一些习题,这些习题都在HDOJ上,课件上有详细说明,想学习的,就下去看看,个人觉得不错。
hdoj上的资源,代码有注释,很不错的哦
ACM ICPC HDOJ1003
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj1004,解题代码,答案代码,欢迎下载
hdoj解题代码,题目为1000-1050
HDOJ从零到零 <<< <<< <<< >>> >>> >>> :calendar:阶段性计划 :bullseye: 2021-04-30〜30题
ACM ICPC HDOJ1008
codj,hdoj的源码(50-60题)
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj杭电1000-2000部分解题报告 部分是cpp 格式 部分是文档格式