首页 > 搜索 > BFS搜索 > hdu 2463 USTC campus network-BFS-[解题报告]C++
2014
01-26

hdu 2463 USTC campus network-BFS-[解题报告]C++

USTC campus network

问题描述 :

USTC campus network is a huge network. There is a bi-directional link between every pair of computers in the network. One of the computers is the BBS server, which is so popular that thousands of people log on it every day. Recently some links of the network are damaged by the rainstorm. The network administrator is going to check which computers are still connected with the BBS server directly or indirectly.

You are to help the administrator to report the number of computers still connecting with the BBS server (not including itself).

输入:

The 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.

输出:

The 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.

样例输入:

3 2
1 2
1 3
4 3
1 2
3 2
4 2
0 0

样例输出:

Case 1: 0
Case 2: 2

题意:http://acm.hdu.edu.cn/showproblem.php?pid=2463

      原来是一个完全图,去掉一些边,问最后跟1相连的点有几个。

题解:

      bfs+数据结构。感觉数据结构还是很神的。用vector存删去的边,用pre去判断和队列顶点相连的点。好神。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#define maxn 10010
using namespace std;
int n,m,a,b;
int pre[maxn];
vector <int> map[maxn];
bool vis[maxn];
int solve(){
    queue <int> q;
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    vis[1] = 1;
    q.push(1);
    int ans = 0;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0; i < map[now].size(); i ++)
            pre[map[now][i]] = now;
        for(int i = 1; i <= n;i ++)
            if(!vis[i] && pre[i] != now)
                vis[i] = true, q.push(i),ans ++;
    }
    return ans;
}
int main(){
    int ca = 1;
    while(~scanf("%d%d",&n,&m) && (n || m)){
        for(int i = 1; i <= n; i ++)
            map[i].clear();
        for(int i = 0; i < m; i ++){
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        printf("Case %d: %d\n",ca ++ ,solve());
    }
    return 0;
}

解题转自:http://blog.csdn.net/julyana_lin/article/details/7982131


,