简答题 偏难
#20213

线图 时间限制:1 s,内存限制:512 MB 【问题描述】 给定由 n 个结点与 m 条边构成的简单无向图 G,结点依次以 1、2、……、n 编号。简单无向图…

线图

时间限制:1 s,内存限制:512 MB

【问题描述】

给定由 n 个结点与 m 条边构成的简单无向图 G,结点依次以 1、2、……、n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建:

(1)初始时线图 L(G) 为空。

(2)对于无向图 G 中的一条边,在线图 L(G) 中加入与之对应的一个结点。

(3)对于无向图 G 中两条不同的边 (u1, v1)、(u2, v2),若存在 G 中的结点同时连接这两条边(即 u1, v1之一与 u2, v2之一相同),则在线图 L(G) 中加入一条无向边,连接  (u1, v1)、(u2, v2) 在线图中对应的结点。

请你求出线图 L(G) 中所包含的无向边的数量。

【输入描述】

第一行,两个正整数 n、m,分别表示无向图 G 中的结点数与边数。

接下来 m 行,每行两个正整数 ui、vi,表示 G 中连接 ui、vi 的一条无向边。

【输出描述】

输出共一行,一个整数,表示线图 L(G) 中所包含的无向边的数量。

【样例输入1】

5 4
1 2
2 3
3 1
4 5

【样例输出1】

3

【样例输入2】

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

【样例输出2】

30

【样例解释1】

【数据范围】

对于60%测试点,保证 1 <= n、m <= 500。

对于所有测试点,保证 1 <= n、m <= 100000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; const int N = 1e5 + 5; int n, m, deg[N]; long long ans; int main() {     cin &gt;&gt; n &gt;&gt; m;     while (m--) {         int u, v;         cin &gt;&gt; u &gt;&gt; v;         deg[u]++;         deg[v]++;     }     for (int i = 1; i &lt;= n; i++)         ans += 1ll * deg[i] * (deg[i] - 1) / 2;     cout &lt;&lt; ans;     return 0; }</pre>
这道题暂未补解析。