国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 學(xué)院 > 開(kāi)發(fā)設(shè)計(jì) > 正文

A Bug's Life

2019-11-10 19:42:34
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

A Bug's Life

時(shí)間限制:1000 ms  |  內(nèi)存限制:65535 KB難度:4描述 Background PRofessor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs. Problem Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.輸入The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 10000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.輸出The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.樣例輸入
23 31 22 31 34 21 23 4樣例輸出
Scenario #1:Suspicious bugs found!Scenario #2:No suspicious bugs found!

解題報(bào)告:種類(lèi)并查集。把性別相同的蟲(chóng)子放在同一個(gè)集合,然后每讀入一對(duì)蟲(chóng)子號(hào),判斷它們?cè)诓辉谕患希趧t同性別,不在則繼續(xù)。

code

#include<iostream>#include<stdio.h>#include<queue>#include<vector>#include<stack>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int MAXN = 10005; /*結(jié)點(diǎn)數(shù)目上限*/int pa[MAXN];    /*pa[x]表示x的父節(jié)點(diǎn)*/int rank[MAXN];    /*rank[x]是x的高度的一個(gè)上界*/int gender[MAXN];  // 與i性別相反的蟲(chóng)子號(hào)/*創(chuàng)建一個(gè)單元集*/void make_set(int x){    pa[x] = x;    rank[x] = 0;    gender[x]=0;}/*帶路徑壓縮的查找*/int find_set(int x){    if(x != pa[x]){        pa[x] = find_set(pa[x]);    }    return pa[x];}/*按秩合并x,y所在的集合*/void union_set(int x, int y){    x = find_set(x);    y = find_set(y);    if(rank[x] > rank[y])/*讓rank比較高的作為父結(jié)點(diǎn)*/    {        pa[y] = x;    }    else    {        pa[x] = y;        if(rank[x] == rank[y])            rank[y]++;    }}int main(){  //  freopen("input.txt","r",stdin);    int t,m,n,k=1;    scanf("%d",&t);    while(t--){        scanf("%d%d",&m,&n);        for(int i=1;i<=m;i++){ //初始化            make_set(i);        }        int a,b,flag=1;        for(int i=0;i<n;i++){            scanf("%d%d",&a,&b);            if(!flag) //結(jié)果出來(lái)之后也要把數(shù)據(jù)讀完                continue;            if(find_set(a)==find_set(b)){  //判斷兩個(gè)蟲(chóng)子在不在同一個(gè)集合                flag=0;                continue;            }            if(gender[a]==0) gender[a]=b; //把性別相同的蟲(chóng)子放在同一個(gè)集合里            else union_set(gender[a],b);            if(gender[b]==0) gender[b]=a;            else union_set(gender[b],a);        }        if(k!=1)            printf("/n");        if(flag)            printf("Scenario #%d:/nNo suspicious bugs found!/n",k++);        else            printf("Scenario #%d:/nSuspicious bugs found!/n",k++);    }    return 0;}


發(fā)表評(píng)論 共有條評(píng)論
用戶(hù)名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 马龙县| 南丹县| 安乡县| 桑植县| 北流市| 顺昌县| 高密市| 修文县| 永兴县| 白沙| 龙州县| 达拉特旗| 华坪县| 仁化县| 华阴市| 浑源县| 宜阳县| 和林格尔县| 米林县| 隆尧县| 依兰县| 涪陵区| 景德镇市| 周口市| 克东县| 红原县| 华安县| 青河县| 新津县| 苍南县| 乌什县| 柳州市| 都安| 四子王旗| 绩溪县| 四平市| 武强县| 内江市| 拜泉县| 许昌市| 湟中县|