UVa 359 Sex Assignments And Breeding Experiments

题目描述每个人都知道家谱的图示表示。在这些“图片”中使用点和线来表示家庭结构和家庭间的关系。例如如果MMM和FFF是三个孩子两个男孩和一个女孩的父母图形如下所示。很容易想到大量的此类图形。有些可以表示家谱有些则不能。你的任务是描述那些可以表示家谱的图形的特征。为简化问题我们假设处理的是一个完全由双性繁殖MMM和FFF特征化的种群。如果通过对种群成员进行适当的性别分配图形能够表示理论上可能发生的繁殖实验结果则称该图形是sexy性感的否则是not sexy。你需要编写一个程序来检查任意有向图判断它是否为sexy。注意有向边x→yx \to yx→y表示xxx是yyy的父母每个个体通常恰好有两个父母每个个体不能有两个同性别父母也不能有两个以上的父母繁殖实验不会无限延伸到过去总会达到某个点其中种群成员的一个或两个父母是未知的即没有父母的节点假定个体的出生在时间上是顺序的输入格式输入包含一系列图形描述格式如下第一行两个整数nnn节点数和mmm有向边数接下来mmm行每行两个整数xxx、yyy表示从节点xxx到yyy的一条有向边输入以文件结束符EOF\texttt{EOF}EOF结束。输出格式对于输入文件中的每个图形输出以下语句之一Graph number i is sexyGraph number i is not sexy其中iii是图形在输入文件中的编号。样例输入5 6 1 3 2 3 1 4 2 4 1 5 2 5 3 3 1 2 2 3 3 1样例输出Graph number 1 is sexy Graph number 2 is not sexy题目分析问题的本质这是一个有向图约束满足问题。给定一个有向图需要判断是否存在一种给每个节点分配性别M\texttt{M}M或F\texttt{F}F的方式使得每条边表示“父母-子女”关系xxx是yyy的父母每个节点最多有两个父节点入度 ≤ 2如果一个节点有两个父节点它们的性别必须不同一个MMM一个FFF图必须是无环的DAG\texttt{DAG}DAG因为出生顺序要求时间上的先后关系约束条件总结设每个节点iii有一个布尔变量xix_ixi​表示性别例如000表示MMM111表示FFF入度约束每个节点的入度≤2≤ 2≤2性别异或约束如果节点iii有两个父节点aaa和bbb则xa≠xbx_a \neq x_bxa​xb​即xa⊕xb1x_a \oplus x_b 1xa​⊕xb​1无环性图中不能有有向环因为出生顺序不能形成循环依赖问题分解检查入度每个节点入度≤2≤ 2≤2检查DAG\texttt{DAG}DAG图中不能有环2-SAT\texttt{2-SAT}2-SAT可满足性对于有两条入边的节点它们的父节点性别必须不同形成xa≠xbx_a \neq x_bxa​xb​的约束。这是一个典型的2-SAT\texttt{2-SAT}2-SAT问题。2-SAT\texttt{2-SAT}2-SAT建模对于约束xa≠xbx_a \neq x_bxa​xb​等价于(xa∨xb)∧(¬xa∨¬xb)(x_a \lor x_b) \land (\neg x_a \lor \neg x_b)(xa​∨xb​)∧(¬xa​∨¬xb​)在2-SAT\texttt{2-SAT}2-SAT中每个变量有两个文字xxx真和¬x\neg x¬x假。约束(a∨b)(a \lor b)(a∨b)转化为两条蕴含边¬a→b\neg a \to b¬a→b¬b→a\neg b \to a¬b→a对于xa≠xbx_a \neq x_bxa​xb​即(xa∨xb)∧(¬xa∨¬xb)(x_a \lor x_b) \land (\neg x_a \lor \neg x_b)(xa​∨xb​)∧(¬xa​∨¬xb​)从¬xa\neg x_a¬xa​到xbx_bxb​从¬xb\neg x_b¬xb​到xax_axa​从xax_axa​到¬xb\neg x_b¬xb​从xbx_bxb​到¬xa\neg x_a¬xa​参考代码// Sex Assignments and Breeding Experiments// UVa ID: 359// Verdict: Accepted// Submission Date: 2018-05-04// UVa Run Time: 0.060s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;boolsexy;vectorintcolor,degree,dfn,low,scc;intdfstime,cscc;vectorvectorintedges,parents;// edges: 原图, parents: 父节点列表stackints;// Tarjan 算法求强连通分量voidtarjan(intu){dfn[u]low[u]dfstime;s.push(u);for(autov:edges[u]){if(!dfn[v])tarjan(v),low[u]min(low[u],low[v]);elseif(!scc[v])low[u]min(low[u],dfn[v]);}if(dfn[u]low[u]){cscc;while(true){intvs.top();s.pop();scc[v]cscc;if(uv)break;}}}// DFS 检查是否有环DAGvoiddfs(intu){if(!sexy)return;color[u]0;// 正在访问for(autov:edges[u])if(color[v]-1)dfs(v);elseif(color[v]0)// 发现环sexyfalse;color[u]1;// 访问完成}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0,x,y,n,m;while(cinnm){// 初始化edges.assign(n,vectorint());parents.assign(n,vectorint());degree.assign(n,0);sexytrue;// 读取边for(inti1;im;i){cinxy;x--,y--;edges[x].push_back(y);degree[y];// 入度不能超过 2if(degree[y]2)sexyfalse;parents[y].push_back(x);}// 检查 DAGif(sexy){color.assign(n,-1);for(inti0;in;i)if(color[i]-1)dfs(i);}// 2-SAT 检查if(sexy){// 构建 2-SAT 蕴含图共 2n 个节点dfstime0,cscc0;while(!s.empty())s.pop();edges.assign(2*n,vectorint());dfn.assign(2*n,0);low.assign(2*n,0);scc.assign(2*n,0);// 对于有两条入边的节点添加 x_p1 ! x_p2 约束for(inti0;in;i)if(parents[i].size()1){intb1parents[i][0],b2parents[i][1];// x_b1 ! x_b2 转换为蕴含边edges[b1n].push_back(b2);edges[b2n].push_back(b1);edges[b2].push_back(b1n);edges[b1].push_back(b2n);}// 求强连通分量for(inti0;i2*n;i)if(!dfn[i])tarjan(i);// 检查是否有矛盾for(inti0;in;i)if(scc[i]scc[in]){sexyfalse;break;}}coutGraph number cases is ;cout(sexy?sexy:not sexy)\n;}return0;}