ACM_Someone like you

/*
題意：往倉庫里放炸藥，把關鍵引爆炸藥的數對拿出并計數
數學模型：輸入數對，判斷是否成環eg（1,2  2,3  3,4,  1,4）這個時候要計數。
該題中讓人費解反復的的是n種材料是不是都出現才會引爆？不是
eg（1,2 2,4 1,4）也要累加計數。
核心算法：并查集、判環 前面的數和當前的這個數只要都是一個根節點時就判為環 否則歸并
為一個集合一個根節點-1止。
輸入時候注意：循環輸入EOF，開始時用了while(1)超時了沒有節制注意一下
Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu)
:: Chapter 3. Data Structures :: Fundamental Data Structures :: Examples        
*/
//AC不容易
#include<stdio.h>
#include<string.h>
const int M=100010;//100000+10;
int ct;
int fa[M];
void inist()
{
    int i;
    for(i=0;i<M;i++)
    fa[i+1]=i+1;
}
int find(int x)//查根節點
{
    while(fa[x]!=x)
    x=fa[x];
    return x ;
    //else return x;
}
void Union(int a,int b)//并查集
{
    int i,j,k;
    int f1,f2;
    f1=find(a);
    f2=find(b);
    if(f1!=f2)
    {
        fa[f1]=fa[f2];
    }
    else ct++;
}
int main()
{
    int a,b;
    while(scanf("%d",&a)!=EOF)//此處必須EOF的方式處理
    //不然就會判定為超時！！！
    {
        ct=0;
        inist();//初始化所有根節點
        while(a!=-1)
        {
            scanf("%d",&b);//if(a==-1)break;
            Union(a,b);//并查集
            scanf("%d",&a);
        }
        printf("%d\n",ct);
        }
    return 0;
}
/*
int main()
{
    int a,b;
    while(1)
    {
        ct=0;
        inist();//初始化根節點
        while(1)//超時！！！！
        {

            scanf("%d",&a);
            if(a==-1)break;
            scanf("%d",&b);
            Union(a,b);
        }
        printf("%d\n",ct);

    }
    return 0;
}//*/