HDoj 1829 A Bug's Life【権限を持ってセットを調べる】

A Bug's Life
Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10618    Accepted Submission(s): 3451
Problem 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.
 
Sample Input

   
   
   
   

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

 
Sample Output

   
   
   
   

    
    
    
    Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!


    
    
    
    
 
     
 
      Hint 
     
Huge input,scanf is recommended. 
    
    
    
    
     
   
   
   
   

 
この問題は簡単な調査集ではありません.これは性別という情報を維持する必要があるからです.
最初は性別情報を1つの配列sexで直接格納し,この配列を0に初期化した.1はオス、-1はメスを表します.
2つの未鑑別性別(すなわちsex[x]==0&&sex[y]==0)に遭遇すると、直接sex[x]=1、sex[y]=-1となる.
性別を鑑別していない(すなわちsex[x]==0またはsex[y]==0)sex[x]==0の場合、sex[x]=-sex[y],yと同じである.
次はリングになっているかどうかを判断して提出したら、その後はありません...
データのセットで言えば
4 3
1 2
3 4
1 3
このグループには怪しい同性愛者はいませんが、私のコードはありますので、私のコードは間違っています.
正しい考え方:1つの配列loveで現在の要素の最初の恋愛の対象が存在します.
毎回x,yを判断する:
love[x]==0であれば、その要素がまだ恋愛されていないことを示し、現在の恋愛対象yをlove[x]に付与する.
0でなければ、その要素が恋愛するオブジェクトと現在の恋愛オブジェクトをマージするmerge(love[x],y);
y要素の判断はxと同じである.
 
2つのコードを添付します.

#include <cstdio>
#include <cstring>
#define MAX 2000+10
using namespace std;
int set[MAX];
int love[MAX];//      i     
int n, m;
int k = 1;
int exist;
void init()
{
    int i;
    for(i = 1; i <= n; i++)
    {
        set[i] = i;
        love[i] = 0;//    0 
    }
}
int find(int p)
{
    int t;
    int child = p;
    while(p != set[p])
    p = set[p];
    while(child != p)
    {
        t = set[child];
        set[child] = p;
        child = t;
    }
    return p;
} 
void merge(int x, int y)//     
{
    int fx = find(x);
    int fy = find(y);
    if(fx != fy)
    set[fx] = fy;
} 
void search()
{
    int i, x, y;
    exist = 0; 
    for(i = 0; i < m; i++) 
    {
        scanf("%d%d", &x, &y);
        if(exist)//                
        continue; 
        if(find(x) == find(y))//          
        {
            exist = 1;//    
            continue; 
        }
        if(love[x])//x     
        {
            merge(love[x], y);// x       y             
        }
        else love[x] = y;
        if(love[y])//y      
        {
            merge(love[y], x);// y       x             
        } 
        else love[y] = x; 
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        init();
        search();
        printf("Scenario #%d:
", k++);
        if(!exist)
        printf("No suspicious bugs found!
");
        else
        printf("Suspicious bugs found!
");
        printf("
"); 
    }
    return 0;
}

 
2:

        2   i-A,i-B，   2   N         。
           ： 
1，i-x   i    x 。
2，                              。 
  ，  i-A i-B      ，     i    A  j      B，  j    B  i      A。
  ，       ，               。 
   ：x y       x-A y-B,x-B y-A；（x  x-A，x+n  x-B） 
   ：  ，  x-A y-A,x-A y-B； 

    ：

<pre class="cpp" name="code">#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 4000+10
using namespace std;
int set[MAX];
int n, m;
int k = 1;
void init()
{
	for(int i = 1; i <= 2*n; i++)
	set[i] = i;
}
int find(int p)
{
	int t;
	int child = p;
	while(p != set[p])
	p = set[p];
	while(child != p)
	{
		t = set[child];
		set[child] = p;
		child = t;
	}
	return p;
}
void merge(int x, int y)
{
	int fx = find(x);
	int fy = find(y);
	if(fx != fy)
	set[fx] = fy;
}
bool same(int x, int y)
{
	return find(x) == find(y);
}
void input()
{
	int x, y;
	int exist = 0;
	while(m--)
	{
		scanf("%d%d", &x, &y);
		if(exist) continue;
		if(same(x, y))
		{
			exist = 1;
			continue;
		}
		merge(x, y+n);
		merge(x+n, y);
	}
	printf("Scenario #%d:
", k++);
	if(exist)
	printf("Suspicious bugs found!

");
	else
	printf("No suspicious bugs found!

");
}
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n, &m);
		init();
		input();
	}
	return 0;
}