作业graph position解题报告

1、GraphitionTime Limit: 0.5 second Memory Limit: 1 000 KBThere is a simple graph wi n even number of edges. You are to define if it is sible to present it by the set of pairs of adjacent edges (having a common vertex).Inputcontains a sequence of the numbers pairs. Each pair denotes vertiidentifiers of

2、 one edge. All the identifiers areegers from 1 to 1000.You may amet the input is correct, i.e there are noloops andmultiple edgeshe graph definedby theinput data.Output“1”“0”(withoutquoionmarks),iftheitionissibleandotherwise.Sle InputS 1231le input #123110S 1234le input #223110Sle OutputS 1le output

3、 #1Sle output #20试题简介（URAL1320）：给定一个无向图，并且满足：（1）（2）（3）图中不存在重边和连向自身的弧总边数为偶数结点不超过 1000 个问你能否将图中的边划分成两个一组，使得每组中的两条边在原图中有公共结点。分析：从问题的规模看，用枚举明显是不可能的。可以肯定的是，若某个连通块中包含了奇数条边，该图一定无解（无论怎么分，最后至少会留下一条弧没法配对）。反过来思考，如果图中的所有连通块都包含了偶数条边，是不是一定有解呢？通过列举几个简单数据，发现确实如此，下面就要尝试着证明这个结论。对图中的每通块做一次 DFS 遍历，得到其对应的搜索树。由于图中可以有环，所以

4、这棵树上可能存在后向弧。定义每次操作先找到树中深度最深的点X（显然X 为叶子结点），设 X 的父亲为Y。那么可能出现如下情况：（1）（2）（3）X 有多于 2 条后向弧，去掉这两条后向弧。X 只有 1 条后向弧，去掉这条后向弧，并去掉 X 和Y 之间的弧。X 没有后向弧，但是 Y 有后向弧，去掉 X、Y 之间的弧和 Y 的一条后向弧。X、Y 都没有后向弧，但是 Y 除了 X 以外还有至少 1 个儿子结点。由于 X 是最深点，所以 Y 的其它儿子也是叶子结点，去掉 X、Y 的连边，Y与它另外一个儿子的连边。X、Y 都没有后项弧，而且 Y 除了 X 外没有儿子结点，由于前面假定了该连通块中包含偶数

5、条边，前面 4 步每次都删除 2 条边，因此 Y 必定（4）（5）不是根结点（否则就只剩它连X 的这一条边了，与假设以去掉X 与 Y 之间以及 Y 与 Y 父亲之间的连边。），可每进行一次操作，就成功将两条边划分为一组，并且剩下的仍然是一棵树，只要像这样不断地操作下去，直到子图中所有弧都被剔除，就能得到一个满足条件的方案。综合上面的分析，就可以得到如下结论：图G 存在一个合法划分方案的充要条件是，G 中的每个连通块都包含了偶数条边。接下来就很简单了，采用最简单的并查集，就可以用O（N）的空间复杂度， O（M）的时间复杂度高效地解决该问题。参考程序：$r-,s-,q- const infnsou

6、tfns maxnvar tree, edge=:input.txt;output.txt; 1000;array1. maxn ofeger;function findroot(x var root, now, temp beginnow :=x;while treenow :eger) :eger; 并查集子过程eger;0do now :=treenow;root :=now; now :=x; while now root do begintemp :=treenow; treenow :=root; now end;whilefindroot :=root;end;findroot:

7、=temp;procedure main; 并查集主过程var rootx, rooty, x, y :begineger;assign(input, infns); reset(input);fillchar(tree, sizeof(tree), fillchar(edge, sizeof(edge), while not eof do beginreadln(x, y);rootx :=findroot(x); rooty$ff);0);:=findroot(y);if rootx rooty then beginif treerootx treerooty then beginedge

8、rootx treerootxtreerooty:=edgerootx:=treerootx:=rootx;+edgerooty +treerooty;1;endthen else beginedgerooty treerooty treerootxend;else:=edgerootx:=treerootx:=rooty;+edgerooty +treerooty;1;end else inc(edgerootx); end;whileclose(input);end;mainprocedure out;var i, ansbegin:eger; assign(output, outfns); rewrite(output);ans :=1;for i