你们镇上的一些居民已经制作了给彼此的圣诞礼物。但今天镇长宣布,他镇上的每个居民,必须制作和他收到的礼物一样多的礼物。现在他们需要你的编程技巧来计算出基于他们已经制作出的礼物数量,还缺少多少礼物来满足市长的要求。
输入:
一行包含N和M(2≤N≤10^5,1 ≤M≤ 3*10^5)--人的数量和他们已经制作的礼物的数量
M行描述礼物,第i行包含整数xi和yi (1 ≤ xi , yi ≤ N), 代表着xi已经给yi做了礼物
输出:
缺失的礼物的数量。一个人可以收到来自同一个人的多份礼物。
你们镇上的一些居民已经制作了给彼此的圣诞礼物。但今天镇长宣布,他镇上的每个居民,必须制作和他收到的礼物一样多的礼物。现在他们需要你的编程技巧来计算出基于他们已经制作出的礼物数量,还缺少多少礼物来满足市长的要求。
输入:
一行包含N和M(2≤N≤10^5,1 ≤M≤ 3*10^5)--人的数量和他们已经制作的礼物的数量
M行描述礼物,第i行包含整数xi和yi (1 ≤ xi , yi ≤ N), 代表着xi已经给yi做了礼物
输出:
缺失的礼物的数量。一个人可以收到来自同一个人的多份礼物。
#include<iostream>
#include<math.h>
#define MAX_N 100000
#define MAX_M 300000
using namespace std;
int inDegree[MAX_N] = { 0 }, outDegree[MAX_N] = { 0 };
int main() {
int n, m,i,x,y,num=0;
cin >> n >> m;
for (i = 0; i < n; i++)
inDegree[i] = outDegree[i] = 0;
for (i = 0; i < m; i++) {
cin >> x >> y;
inDegree[y - 1] += 1;
outDegree[x - 1] += 1;
}
for (i = 0; i < n; i++) {
num += abs(inDegree[i] - outDegree[i]);
}
cout << num/2 << endl;
}