InputThe input consists of multiple test cases. Each test case starts with a line containing two integers N and M (1 ≤ N ≤ 10,000, 0 ≤ M ≤ 1,000,000), which are the number of computers and the number of damaged links in USTC campus network, respectively. The computers are numbered from 1 to N and computer 1 is the BBS server.
Each of the following M lines contains two integers A and B(1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B), which means the link between computer A and B is damaged. A link will appear at most once.
The last test case is followed by a line containing two zeros.OutputFor each test case, print a line containing the test case number( beginning with 1) followed by the number of computers still connecting with the BBS server.Sample Input
3 2 1 2 1 3 4 3 1 2 3 2 4 2 0 0
Sample Output
Case 1: 0 Case 2: 2
要用邻接表存一下不能走的地方，然后预处理一下，直接用二维的数组存会MLE，还有尽量用C++交，G++容易T
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<set> #include<map> #include<vector> #include<cmath> #define Inf 0x3f3f3f3f const int maxn=1e4+5; typedef long long ll; using namespace std; bool book[maxn]; bool vis[maxn]; vector<int>vec[maxn]; int n,m; int bfs() { queue<int>q; book[1]=true; q.push(1); int ans=0; while(!q.empty()) { int tmp=q.front(); q.pop(); memset(vis,false,sizeof(vis)); for(int t=0;t<vec[tmp].size();t++) { vis[vec[tmp][t]]=true; } for(int t=1;t<=n;t++) { if(vis[t]==false&&book[t]==false) { ans++; q.push(t); book[t]=true; } } } return ans; } int main() { int cnt=1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) { break; } for(int t=1;t<=n;t++) { vec[t].clear(); } memset(book,false,sizeof(book)); int a,b; for(int t=0;t<m;t++) { scanf("%d%d",&a,&b); vec[a].push_back(b); vec[b].push_back(a); } int ans=bfs(); printf("Case %d: %d\n",cnt++,ans); } return 0; }
原文：https://www.cnblogs.com/Staceyacm/p/10873769.html