FOJ Problem 2210 攻占计划

一，问题描述

二，问题分析

       分析题目n表示城市数量，m表示城市之间道路的数量，而道路不会形成环路，且输入的a,b表示表示城市a有一条连向城市b的道路，说明是有向图，要破坏一座城市，使得断粮最多，即就是选择一个城市，而这个城市就是 道路中起点次数最多的城市，采用一个数组记录城市作为起点的次数，注意城市的下标是从1开始的，所以数组要多开辟一个空间。

三，问题解答

#include<iostream>
#include<vector>
using namespace std;

int main() {
	int n, m;			//n 城市数，m道路数
	cin >> n >> m;
	vector<int> start(n + 1);			//数组多开辟一个空间
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		start[a]++;
	}
	int max = 0;
	int maxid = 0;
	for (int i = 0; i < start.size(); i++) {		//选出起点数最多的城市，并记录下标
		if (start[i] > max) {
			max = start[i];
			maxid = i;
		}
	}
	cout << maxid << endl;					//输出城市编号


	return 0;
}