항 저 우 전기 1878 오 라 회 로 (오 라 회 로 의 판단)

오 라 회 로
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11399    Accepted Submission(s): 4165
Problem Description
오 라 회 로 는 펜 이 지면 을 떠 나 지 못 하 게 그림 의 각 변 을 한 번 만 그 릴 수 있 고 출발점 으로 돌아 갈 수 있 는 회 로 를 말한다.이제 오 라 회 로 가 있 는 지 그림 을 정 해 주 시 겠 습 니까?
 
Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 번 째 줄 은 두 개의 정수 로 노드 수 N (1 < N < 1000) 과 변수 M 을 제시한다.그 다음 에 M 줄 은 M 개의 변 에 대응 하고 각 줄 은 한 쌍 의 정 수 를 제시 하 는데 각각 이 변 이 직접 연 결 된 두 노드 의 번호 (노드 는 1 에서 N 번호) 이다.N 이 0 일 때 입력 매듭
다발
 
Output
모든 테스트 용례 의 출력 은 한 줄 을 차지 하고, 오로라 회로 가 존재 하면 1 을 출력 하고, 그렇지 않 으 면 0 을 출력 한다.
 
Sample Input

   
   
   
   

    
    
    
    3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
0
   
   
   
   

 
Author
ZJU
여기 서 먼저 오로라 도로 가 무엇 인지 구술 해 보 자. 모든 점 을 연결 하 는 도로. (고리 가 되 지 않 는 다).
즉, 모든 점 을 연결 하 는 고리 로 오 라 회 로 라 고 할 수 있다.
우 리 는 집합 을 찾 는 작업 이 두 점 을 연결 하 는 작업 을 쉽게 해결 할 수 있다 는 것 을 알 고 있 습 니 다. 그래서 여 기 는 집합 을 찾 아 이 문 제 를 풀 수 있 습 니 다.
아래 는 두 점 을 연결 하 는 작업 입 니 다.

void merge(int a,int b)
{
    int A,B;
    A=find(a);
    B=find(b);
    if(A!=B)
    f[B]=A;
}

다음은 find 작업 (경로 압축 포함) (물론 이 문 제 는 경로 압축 없 이도 통과 할 수 있 습 니 다)

int find(int a)
{
    int r=a;
    while(f[r]!=r)
    r=f[r];
    int i=a;
    int j;
    while(i!=r)
    {
        j=f[i];
        f[i]=r;
        i=j;
    }
    return r;
}

그리고 문 제 를 푸 는 관건 적 인 배열 을 소개 합 니 다.

int f[12121212];//并查集数组
int path[121212];//判断点出现次数的数组

문제 풀이 방향:
우 리 는 다음 과 같은 예 가 하나의 회 로 를 구성 할 수 있다 는 것 을 안다.
1 2
2 3
1 3
이때 우 리 는 각 점 의 출현 횟수 가 2 라 는 것 을 안다.
여기에 반 례 를 하나 더 드 리 겠 습 니 다. 하나, 둘.
2 3
이 예 2 는 두 번 나 왔 고 13 은 두 번 나 오지 않 았 다.
여기에 반 례 를 하나 더 드 리 겠 습 니 다.
1 4
1 2
2 4
1 3
2 3
이 예 에는 네 번 밖 에 나타 나 지 않 았 고 다른 것 은 여러 번 나 타 났 다.
독자 가 있 는 이곳 에 서 는 스스로 몇 가지 예 를 더 취하 여 증명 할 수 있다.
이 를 통 해 알 수 있 듯 이 모든 노드 가 두 번 나 타 났 을 때 만 하나의 회 로 를 구성 했다 (있 고 하나 밖 에 없다 ~).
이때 우 리 는 한 그룹의 데 이 터 를 읽 을 때마다 노드 가 나타 난 횟수 를 통계 하고 노드 의 링크 를 해 야 한다.
최종 적 으로 링 이 되 었 는 지 여 부 를 판단 할 때 집합 과 관련 된 작업 을 해 야 한다. 링크 노드.
모든 읽 은 데이터 의 노드 가 연결 되 었 을 때 집합 배열 은 유일한 노드 를 가리 킬 것 입 니 다.
이때 다음 과 같은 판단 이 나 왔 다.

        int huan=0;
        int tongji=0;
        for(int i=0;i<n;i++)
        {
            if(f[i]==i){huan++;if(huan>1)break;}
            if(path[i]!=2)tongji++;
        }
        if(huan>1)
        {
            printf("0
");
            continue;
        }
        if(tongji==0)
        printf("1
");
        else
        printf("0
");

그리고 여기에 완전한 AC 코드 를 붙 입 니 다.

#include<stdio.h>
#include<string.h>
using namespace std;
int f[12121212];
int path[121212];
int n,m;
void init()
{
    for(int i=0;i<n;i++)
    f[i]=i;
}
int find(int a)
{
    int r=a;
    while(f[r]!=r)
    r=f[r];
    /*int i=a;
    int j;
    while(i!=r)
    {
        j=f[i];
        f[i]=r;
        i=j;
    }*/
    return r;
}
void merge(int a,int b)
{
    int A,B;
    A=find(a);
    B=find(b);
    if(A!=B)
    f[B]=A;
}
int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0)break;
        scanf("%d",&m);
        init();
        memset(path,0,sizeof(path));
        while(m--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            merge(x,y);
            path[x]++;
            path[y]++;
        }
        int huan=0;
        int tongji=0;
        for(int i=0;i<n;i++)
        {
            if(f[i]==i){huan++;if(huan>1)break;}
            if(path[i]!=2)tongji++;
        }
        if(huan>1)
        {
            printf("0
");
            continue;
        }
        if(tongji==0)
        printf("1
");
        else
        printf("0
");

    }
}