程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1869 六度分離

HDU 1869 六度分離

編輯：C++入門知識

HDU 1869 六度分離

六度分離

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5035 Accepted Submission(s): 2026

Problem Description 1967年，美國著名的社會學家斯坦利·米爾格蘭姆提出了一個名為“小世界現象(small world phenomenon)”的著名假說，大意是說，任何2個素不相識的人中間最多只隔著6個人，即只用6個人就可以將他們聯系在一起，因此他的理論也被稱為“六度分離”理論(six degrees of separation)。雖然米爾格蘭姆的理論屢屢應驗，一直也有很多社會學家對其興趣濃厚，但是在30多年的時間裡，它從來就沒有得到過嚴謹的證明，只是一種帶有傳奇色彩的假說而已。

Lele對這個理論相當有興趣，於是，他在HDU裡對N個人展開了調查。他已經得到了他們之間的相識關系，現在就請你幫他驗證一下“六度分離”是否成立吧。
Input 本題目包含多組測試，請處理到文件結束。
對於每組測試，第一行包含兩個整數N,M(0 接下來有M行，每行兩個整數A,B(0<=A,B 除了這M組關系，其他任意兩人之間均不相識。

Output 對於每組測試，如果數據符合“六度分離”理論就在一行裡輸出"Yes"，否則輸出"No"。
Sample Input

Sample Output

Yes
Yes

Author linle
Source 2008杭電集訓隊選拔賽——熱身賽

一開始用並查集做。。WA了兩次。。其實是floyd算法求傳遞閉包。我們可以假設兩個認識的人距離為1。不認識的為無窮大。 floyd一遍，求完傳遞閉包後，只要距離大於7 的話，就是No。因為第一個人與第七個人中間最多可以隔六個人。。所以與他的距離為7。大於七的話則不滿足六度分離。。

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include
#include 
#include 
#include 
using namespace std;
#define inf 0x6f6f6f
#define mod 10
int mat[105][105];
int main()
{
    int i,j,k;
    int n,m;
    while(cin>>n>>m)
    {
        int a,b,flag;
        flag=1;
        for(i=0; i>a>>b;
            mat[a][b]=mat[b][a]=1;//認識的距離為1.
        }
        for(k=0; kmat[i][k]+mat[k][j])
                        mat[i][j]=mat[i][k]+mat[k][j];  //求閉包
                }
        for(i=0; i7)  //枚舉任意兩個人。大於七就No。
                {
                    flag=0;
                    break;
                }
            }
            if(!flag)
                break;
        }
        if(!flag)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}