洛谷P2451 遗传代码

题目描述
抽象的 primitivus（Primitivus 循环）的遗传代码是一系列自然数 K=(A_1,A_2,\cdots,A_n)K=(A
1
​
,A
2
​
,⋯,A
n
​
)。我们所说的 primitivus 的特征是一个数对 (l,r)(l,r)，表示 l,rl,r 在 AA 中连续出现。即存在一个 ii，使得 A_i=lA
i
​
=l，A_{i+1}=rA
i+1
​
=r。在 primitivus 的遗传代码中没有 (p,p)(p,p) 特征。

任务
写一个程序：

从文本文件读特征列表；
计算所给特征的最短遗传代码长度；
输出答案。
输入格式
第一行有一个正整数 nn，它是 primitivus 的不同特征的数量。

接下来 nn 行，每一行中有两个被空格号隔开的数字 ll 和 rr。数字对 (l,r)(l,r) 是 primitivus 的一个特征。在输入文件中，特征并不重复。

输出格式
共一行一个整数，为 primitivus 最短遗传代码的长度。

输入输出样例
输入 #1复制
12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6
输出 #1复制
15
说明/提示
样例解释
以下是一种符合题意的最短的遗传代码。它符合输入数据中给出的所有的特征：

(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)(8,5,1,4,2,3,9,6,4,5,7,6,2,8,6)

数据范围及约定
对于全部数据，满足 0 \le l \le 10000≤l≤1000，0 \le r \le 10000≤r≤1000。
上代码：

#include
using namespace std;
int n,a[1005],b[1005],ans;
//a记录出度，b记录入度
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int l,r;
		cin>>l>>r;
		a[l]++;
		b[r]++;
	}
	for(int i=1;i<=1000;i++)
	{
		if(b[i]>a[i]) 
        	ans+=b[i]-a[i];
	}
	cout<<ans+n;
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22