网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
刨芋吧 关注：37贴子：4,821
  • 3回复贴，共1页

3775:USTC campus network

只看楼主收藏回复

总时间限制: 4000ms 内存限制: 65536kB
描述
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.
输出
For 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.
样例输入
3 2
1 2
1 3
4 3
1 2
3 2
4 2
0 0
样例输出
Case 1: 0
Case 2: 2
1楼2013-06-01 00:21回复
    #include<stdio.h>
    #include<stdlib.h>
    struct Delink {
    int mi, ma;
    };
    int cmp1(const void * a, const void * b) {
    Delink *a1=(Delink*)a;
    Delink *b1=(Delink*)b;
    if (a1->mi!=b1->mi) return a1->mi-b1->mi;
    else return a1->ma-b1->ma;
    }
    int cmp2(const void * a, const void * b) {
    return *(int*)a-(*(Delink*)b).mi;
    }
    void linktact(int a, int * table, Delink * delink, int sum, int n, int m) {
    int *pa=&a;
    Delink *p, *p1, *p2;
    p1=new Delink;
    p2=new Delink;
    p1->ma=a;
    p2->mi=a;
    p=(Delink*)bsearch(pa, delink, m, sizeof(Delink), cmp2);
    for (int i=2; i<n+1; i++) {
    if (table[i]==1||i==a) continue;
    p1->mi=i; p2->ma=i;
    if (bsearch(p1, delink, p==NULL?m:p-delink, sizeof(Delink), cmp1)==NULL)
    if (p!=NULL&&cmp1((const void*)p2, (const void*)p)==0) p++;
    else {
    table[i]=1;
    sum++;
    linktact(i, table, delink, sum, n, m);
    }
    }
    delete p1;
    delete p2;
    }
    int main () {
    int n, m, a, b, nCases=0, i, *table, sum;
    Delink *delink;
    while (1) {
    scanf("%d%d", &n, &m);
    if (n==0) break;
    nCases++;
    sum=0;
    delink=new Delink[m];
    table=new int[n+1];
    for (i=1; i<n+1; i++) table[i]=0;
    for (i=0; i<m; i++) {
    scanf("%d%d", &a, &b);
    if (a<b) {
    delink[i].mi=a;
    delink[i].ma=b;
    }
    else {
    delink[i].mi=b;
    delink[i].ma=a;
    }
    }
    qsort(delink, m, sizeof(Delink), cmp1);
    linktact(1, table, delink, sum, n, m);
    printf("Case %d: %d\n", nCases, sum);
    delete []table;
    delete []delink;
    }
    return 0;
    }调试中
    2楼2013-06-01 14:56
    回复
      #include<stdio.h>
      #include<stdlib.h>
      struct Delink {
      int mi, ma;
      };
      int cmp1(const void * a, const void * b) {
      Delink *a1=(Delink*)a;
      Delink *b1=(Delink*)b;
      if (a1->mi!=b1->mi) return a1->mi-b1->mi;
      else return a1->ma-b1->ma;
      }
      int sum;
      void linktact(int a, int * table, Delink * delink, int n, int m) {
      Delink *p1, *p2;
      p1=new Delink; p2=new Delink;
      p1->ma=a; p2->mi=a;
      for (int i=1; i<n+1; i++) {
      if (table[i]==1||i==a) continue;
      p1->mi=i; p2->ma=i;
      if ((i<a&&bsearch(p1, delink, m, sizeof(Delink), cmp1)==NULL)||(i>a&&bsearch(p2, delink, m, sizeof(Delink), cmp1)==NULL)) {
      table[i]=1;
      sum++;
      linktact(i, table, delink, n, m);
      }
      }
      delete p1; delete p2;
      }
      int main () {
      int n, m, a, b, nCases=0, i, *table;
      Delink *delink;
      while (1) {
      scanf("%d%d", &n, &m);
      if (n==0) break;
      nCases++;
      sum=0;
      delink=new Delink[m];
      table=new int[n+1];
      table[1]=1; for (i=2; i<n+1; i++) table[i]=0;
      for (i=0; i<m; i++) {
      scanf("%d%d", &a, &b);
      if (a<b) {
      delink[i].mi=a; delink[i].ma=b;
      }
      else {
      delink[i].mi=b; delink[i].ma=a;
      }
      }
      qsort(delink, m, sizeof(Delink), cmp1);
      linktact(1, table, delink, n, m);
      printf("Case %d: %d\n", nCases, sum);
      delete []table; delete []delink;
      }
      return 0;
      }
      3楼2013-06-01 15:45
      回复
        #include<stdio.h>
        #include<string.h>
        #include<stdlib.h>
        #define mod 1000117
        #define smod 10091
        struct ary{ //存储不合适的边
        int x, y;
        }num[mod];
        int next[mod], hash[mod], point[smod], que[smod];
        int endList;
        void insert(int a, int b){
        int code = (a * smod + b) % mod;
        num[endList].x = a;
        num[endList].y = b;
        next[endList] = hash[code];
        hash[code] = endList++;
        }
        int find(int a, int b){
        if(a > b){
        int t = a;
        a = b;
        b = t;
        }
        int code = (a * smod + b) % mod;
        int i;
        for (i = hash[code]; i > -1;i = next[i])
        if(num[i].x == a && num[i].y == b)
        return 0;
        return 1;
        }
        int main(){
        int n, m,i,temp = 0;
        while(scanf("%d%d",&n,&m),n , m){
        ++temp ;
        int x, y;
        endList = 0;
        memset(hash,-1,sizeof hash);
        for(i = 0; i < m; ++i){
        scanf("%d%d", &x, &y);
        if(x > y){
        insert(y, x);
        }
        else{
        insert(x, y);
        }
        }
        int front = 0,rear = 0;
        que[0] = 1;
        for(i = 2; i <= n; ++i){
        point[i]=i;
        }
        int sum = 0;
        while(front <= rear){
        for(i = 2; i <= n; ){
        if(find(que[front],point[i])){
        rear++;
        que[rear] = point[i];
        point[i] = point[n];
        n--;
        sum++;
        }
        else{
        i++;
        }
        }
        front++;
        }
        printf("Case %d: %d\n", temp, sum);
        }
        return 0;
        }
        IP属地:江西4楼2013-06-01 23:01
        回复

          扫二维码下载贴吧客户端

          下载贴吧APP
          看高清直播、视频！
          • 3回复贴，共1页
          发表回复
          发贴请遵守贴吧协议及“七条底线”贴吧投诉
          内  容:
            查看全部
          发 表
          保存至快速回贴