A国和B国正在进行一场战争，A国有n座城市，这些城市被m条有向道路相连，这些道路不会形成环路。其中有一部分城市比较特殊，其拥有粮仓，拥有粮仓的城市不能被其他城市到达，粮食可以从粮仓经过一些道路送往任意一座城市，现在B国的国王想要破坏一座A国的城市，粮食不能经过被破坏的城市。问破坏哪一座城市，可以使得最多的城市断粮。
第一行两个数n和m(n<=1000,m<=10000)
接下来m行，每行两个数字a和b，表示城市a有一条连向城市b的道路
输出一个数，表示被破坏的城市的序号，如果有多个城市满足条件，输出序号最小的那个城市
解题思路：用并查集建树。只要摧毁根节点就可以摧毁最多的城市，那么节点个数最大的树则是摧毁城市最多的
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> #include <functional> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int f[1005],sum[1005]; int Find(int x) { return x==f[x]?x:f[x]=Find(f[x]); } int main() { int n,m,a,b; while (~scanf("%d %d",&n,&m)) { for(int i=1;i<=n;i++) sum[i]=1,f[i]=i; while(m--) { scanf("%d %d", &a, &b); if(Find(a)!=Find(b)) { f[b]=Find(a); sum[Find(a)]+=sum[b]; } } int ma=-1,k; for(int i=1;i<=n;i++) { if(ma<sum[i]) { ma=sum[i]; k=i; } } printf("%d\n",k); } return 0; }