POJ 2492(병렬 검색 세트)
Time Limit: 10000MS
Memory Limit: 65536K
Total Submissions: 20235
Accepted: 6578
Description
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.
Input
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 2000) 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.
Output
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.
그 1703이랑 거의 똑같아...두 번 고치고 냈어요...첫 번째 PE는 출력 데이터 사이에 공백이 있는 것을 주의하지 않았기 때문이고, 두 번째 AC는
#include
#include
#define clear(a,b) memset(a,b,sizeof(a))
#define maxn 200000
int t,k,fa[maxn],enemy[maxn];
int getfa(int a)
{
if (fa[a] == a) return a;
else fa[a] = getfa(fa[a]);
return fa[a];
}
int judge(int a,int b)
{
return getfa(a) == getfa(b);
}
void unite(int a,int b)
{
fa[getfa(b)] = getfa(a);
}
void work()
{
int m,n,i,b,a;
char ch;
clear(enemy,0);
scanf("%d%d",&n,&m);
for(i = 1;i <= n;i++) fa[i] = i;
for(i = 1;i <= m;i++) {
scanf("%d%d",&a,&b);
if (judge(a,b)) {
int temp = m - i;
while (temp--) scanf("%d%d",&a,&b);
printf("Scenario #%d:
Suspicious bugs found!
",k);
return ;
}
if (enemy[a]) unite(enemy[a],b);
if (enemy[b]) unite(enemy[b],a);
enemy[a] = b;
enemy[b] = a;
}
printf("Scenario #%d:
No suspicious bugs found!
",k);
return ;
}
int main()
{
scanf("%d",&t);
for(k = 1;k <= t;k++) {work();if(k < t)printf("
");}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
TestNG 테스트 프레임워크 - 소개테스트 프레임워크란 무엇입니까? 테스트 프레임워크는 테스트 사례를 만들고 설계하는 데 사용되는 일련의 지침 또는 규칙입니다. 인기 있는 사용 가능한 옵션: TestNG는 JUnit 및 NUnit에서 영감을 받은 테스...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.