hdu 1272小希の迷宮

2505 ワード

タイトルの説明:
任意のグループを入力し、2つの接続されたデータを入力し、最後に0,0で終わり、すべての点が1本の木にあるかどうかを判断し、リングを構成しません.
このテーマで注意すべきは、0,0を入力すると問題の意味に合致するはずです.
1,2,2,1,0,0を入力した場合は,問題の意味に合致しないループを構成する.
入力は必ずしも1からでも連続した入力でもない
hdu oj上でいつもWAを提出する時c++をg++に変えてaになるかもしれません
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 100005
int pre[MAXN], vis[MAXN];
int jishu = 0;   //       
int find(int n)
{
    return n == pre[n] ? n : pre[n] = find(pre[n]);   //                   
}

int unionFri(int x,int y)   //                
{
    int findX = find(x);  //          
    int findY = find(y);
    if(findX != findY)  //                  
    {
        pre[findX] = findY;
        jishu++;   //         +1       i    
    }
    return jishu;
}
int main()
{
    int m,n;
    int i=0;
    int sum;
    for(int i=1;i<MAXN;i++)
        pre[i] = i;    //         
    memset(vis, 0 ,sizeof(vis));
    while(scanf("%d%d",&m,&n)&&m!=-1&&n!=-1)
    {
        if (i == 0 && m == 0 && n == 0)   //   0,0        yes
        {
            puts("Yes");
                continue;
        }
        if(m && n)  //       
        {
            i++;   //       ++
            vis[m] = vis[n] = 1;   //                   1                 
            sum = unionFri(m,n);  //                
        }
        else
        {
            if(i == sum)   //                             
            {
                int k =0, tmp = -1;   //tmp      
                for(int j=1;j<MAXN;j++)   //               
                    if (vis[j])   //           
                    {
                        if (tmp == -1)   //                 
                            tmp = find(j);//           
                        else if (tmp!=find(j))  //                           ++      
                        {
                            k++;
                            break;
                        }
                    }
                if(k == 0)
                    printf("Yes
"); else printf("No
"); } else printf("No
"); // no i=0;// jishu = 0; for(int i=1;i<MAXN;i++) pre[i] = i; memset(vis, 0 ,sizeof(vis)); } } return 0; }