poj-2492 A Bug's Life **

POJ - 1703 과 유사 하 다.그러므로 1703 과 같은 해법 의 코드 를 먼저 돌려 라.
————————————————————
돌리다
이 문 제 는 poj 1182 와 매우 유사 하 다. 단지 그 문 제 를 가지 고 세 개의 집합 이 있 을 뿐 인 데, 우리 의 이 문 제 는 두 개 밖 에 없 으 니, 더욱 간단 하지 않 겠 는가!
구체 적 인 방법 은 이러한 데이터 구조의 일반적인 조작 을 숙지 하고 수집 한 후에 확장 해 야 한다.
집합 에 대해 서 는 을 참고 하 십시오. 이것 은 매우 훌륭 한 알고리즘 류 참고서 입 니 다. 그 가 말 하 는 교차 하지 않 는 집합 은 바로 집합 을 찾 는 것 입 니 다.
두 가지 개념 에 주의 하 세 요: 순위 에 따라 합병 하고 경로 에 따라 압축 합 니 다.
1. 순위 에 따라 합병
그리고 조사 집 은 일반적으로 비교적 효율 적 인 나무 구조 로 표시 되 기 때문에 순서대로 합병 하 는 목적 은 퇴화 된 나무 (즉, 링크 와 유사 한 나무) 가 생기 는 것 을 방지 하 는 것 이다. 한 배열 로 각 요소 의 높이 를 기록 하 는 것 (각 요소 의 아이의 수 를 기록 하 는 것 도 있 고 어떤 것 이 문제 풀이 에 편 의 를 줄 수 있 는 지 구체 적 으로 보 는 것) 이다.그리고 합병 할 때 높이 가 작은 나 무 를 높이 가 큰 위 에 접목 시 켜 퇴화 된 나 무 를 방지한다.
2. 경로 압축
또 다른 배열 은 각 요소 의 조상 을 기록 하면 한 걸음 한 걸음 아버 지 를 찾 아 손실 되 는 시간 을 막 을 수 있다.그리고 조사 집 은 각 요소 가 있 는 집합 을 알 아내 면 서로 다른 집합 을 구분 하기 때문에 우 리 는 대표 적 인 요소 (즉 나무 뿌리) 를 사용 하기 때문에 모든 요소 에 대해 우 리 는 조상 을 보존 하고 서로 다른 집합 을 구분 해 야 한다.
그리고 우리 의 이 문 제 는 순수한 집합 알고리즘 을 사용 하지 않 고 확장 시 켰 다.
우 리 는 결코 "1, 순위 에 따라 합병" 을 사용 하지 않 았 다.
우 리 는 '1. 순위 에 따라 합병' 이라는 계 시 를 받 았 다. '순위' 를 보존 하 는 배열 은 요소 가 아버지 노드 에 비해 관 계 를 보존 하 는 것 이다. 우 리 는 이런 관계 (즉, 아버지 노드 의 서로 다른 순위 에 비해 서로 다른 집합 을 구분 하 는 것) 를 이용 하여 두 개의 집합 을 하나 로 합 칠 수 있 는 것 이 아니 겠 는가?(비고: 이 코드 rank = 0 은 부모 노드 와 같은 성별 을 대표 합 니 다)

#include<stdio.h>
int f[2005],r[2005];
int fs(int i)
{
if(f[i]==i)
   return i;
int t=f[i];
f[i]=fs(f[i]);                //      ， f[i]          

//          （  ）  ，r[t]              （  ）  ，r[i] i            ，
//           ，   r[i]          （  ）  。              。
r[i]=(r[t]+r[i])%2; 
return f[i];
}

void un(int x,int y)
{
int a=fs(x),b=fs(y);
f[a]=b;
r[a]=(r[y]-r[x]+1)%2;       //r[a]+r[x] r[y]            1   ，      gay
}


int main()
{
freopen("in.txt","r",stdin);
int cases,n,m,i,k,x,y;
scanf("%d",&cases);
for(k=1;k<=cases;k++)
{
   int flag=0;
   scanf("%d %d",&n,&m);
   for(i=1;i<=n;i++)
   {
    f[i]=i;
    r[i]=0;
   }
   for(i=1;i<=m;i++)
   {
    scanf("%d %d",&x,&y);
    if(fs(x)==fs(y))
    {
     if(r[x]!=(r[y]+1)%2)
      flag=1;
    }
    else
     un(x,y);
   }
   if(flag)
    printf("Scenario #%d:
Suspicious bugs found!

",k);
   else
    printf("Scenario #%d:
No suspicious bugs found!

",k);
}
return 0;
}

————
이 문 제 는 비교적 직관 적 인 해법 도 있다. 즉, 서로 다른 성의 bug 를 서로 다른 집합 에 두 는 것 이다. (이 해법 은 1703 ms 에 그다지 실 용적 이지 않다)
：

#include <cstdio>
#include <cstring>
using namespace std;

const int maxBugNum = 2000 + 5;
int sceNum, bugNum, actNum;
int p[maxBugNum], h[maxBugNum], G[maxBugNum][maxBugNum];// p， h ：     

void makeSet(int i){
    p[i] = i; h[i] = 1;
}
int findSet(int i){        //    
    if(i != p[i])
        p[i] = findSet(p[i]);
    return p[i];
}
void unionSet(int lhs, int rhs){
    lhs = findSet(lhs); rhs = findSet(rhs);
    if(h[lhs] > h[rhs])    //    
        p[rhs] = lhs;
    else{
        p[lhs] = rhs;
        if(h[lhs] == h[rhs]) h[rhs]++;
    }
}

void print(int num, bool flag){
    printf("Scenario #%d:
", num);
    if(flag)
        printf("Suspicious bugs found!
");
    else
        printf("No suspicious bugs found!
");
    if(num < sceNum) printf("
");
}

int main(){
    scanf("%d", &sceNum);
    for(int i=1; i<=sceNum; i++){
        memset(G, 0, sizeof(G));
        scanf("%d%d", &bugNum, &actNum);

        for(int j=1; j<=bugNum; j++)
            makeSet(j);

        int u, v;
        bool flag = 0;
        for(int j=0; j<actNum; j++){
            scanf("%d%d", &u, &v);
            G[u][v] = G[v][u] = 1;
        }

        //  G[u][v]==1   v        ，    
        //  G[u][v]==1    u   v      ，     
        for(u=1; u<=bugNum; u++){
            int first = -1;
            for(v=1; v<=bugNum; v++){
                if(G[u][v]){
                    if(first == -1) first = v;
                    if(findSet(u) == findSet(v)){
                        flag = 1; break;
                    }
                    else if(first != -1){
                        unionSet(first, v);
                    }
                }
            }
        }
        print(i, flag);
    }


    return 0;
}

————