PAT 1013 Battle Over Cities

本文主要是介绍PAT 1013 Battle Over Cities，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这一道题难吗？不难，呜呜呜，但还是卡了好久，去他娘的段错误，孩子被?啄了眼，注意：并没有说M小于1000。

用数组的话不知道开多大，直接用vector。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct Highway{int c1,c2;
};
vector<Highway> highway;
int check[1005]; 
int getRoot(int city)
{if(check[city]==-1) return city;else return check[city] = getRoot(check[city]);
}
void my_union(int c1,int c2)
{int root1 =getRoot(c1);int root2 = getRoot(c2);if(root1!=root2) check[root1] = root2;  //合并 
}
int isOne(int n,int m,int city)
{memset(check,-1,sizeof(check));for(int i=0;i<m;i++)if(highway[i].c1!=city&&highway[i].c2!=city)my_union(highway[i].c1,highway[i].c2);int count = 0;for(int i=1;i<=n;i++)if(i!=city&&check[i]==-1)count++; return count-1; 
}
int main()
{int n,m,k,c1,c2,city;cin>>n>>m>>k;for(int i=0;i<m;i++){cin>>c1>>c2;highway.push_back({c1,c2});}if(n==1&&m==0){cout<<0;return 0;} for(int i=0;i<k;i++){cin>>city;cout<<isOne(n,m,city)<<endl;		}
} 

 

 

这篇关于PAT 1013 Battle Over Cities的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---