84473 - 图的定义Ⅲ

与一个顶点 v 关联的边的条数称作该顶点的 度 (degree)，记作 d(v)．特别地，对于边 (v, v)，则每条这样的边要对 d(v) 产生 2 的贡献．

对于无向简单图，有 d(v) = \left| N(v) \right|．

握手定理（又称图论基本定理）：对于任何无向图 G = (V, E)，有 \sum_{v \in V} d(v) = 2 \left| E \right|．

推论：在任意图中，度数为奇数的点必然有偶数个．

若 d(v) = 0，则称 v 为 孤立点 (isolated vertex)．

若 d(v) = 1，则称 v 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)．

若 2 \mid d(v)，则称 v 为 偶点 (even vertex)．

若 2 \nmid d(v)，则称 v 为 奇点 (odd vertex)．图中奇点的个数是偶数．

在有向图 G = (V, E) 中，以一个顶点 v 为起点的边的条数称为该顶点的 出度 (out-degree)，记作 d^+(v)．以一个顶点 v 为终点的边的条数称为该节点的 入度 (in-degree)，记作 d^-(v)．显然 d^+(v)+d^-(v)=d(v)．

给出一个图G的点数n，其点集为V(G)={1,2,3,...,n},与边集m。

如果输入的是无向图，求孤立点、叶节点、偶点、奇点的数量。

如果输入的是有向图，求每个节点的入度和出度。

第一行包含两个数字n,m，表示点数和边数。

接着m行，每行2个数字u,v表示一条边。

输入的第一行包含四个数字，表示输入的图为无向图时，孤立点、叶节点、偶点、奇点的数量。

接着输出m行，每行两个数字，其中第i行的数字表示输入的图为有向图时，编号为i的节点的入度、出度。

1 \leq n,m \leq 100, 1 \leq u,v \leq n

原创