1 /* 2 目大意：輸入一個數t，表示測試組數。然后每組第一行兩個數字n,m，n表示有n只昆蟲，編號從1—n,m表示下面要輸入m行交配情況，每行兩個整數，表示這兩個編號的昆蟲為異性，要交配。 3 要求統計交配過程中是否出現沖突，即是否有兩個同性的昆蟲發生交配。 4 5 思路：并查集 6 將同性的昆蟲放入集合之中，如果輸入的昆蟲u, v同時出現在了集合中，那么 u，v就是同性的！發生了同性交配的可能！ 7 */ 8 9 #include <string> 10 #include <cstdio> 11 #include <cstring> 12 #include <iostream> 13 14 15 16 using namespace std; 17 int n, m; 18 int f[2010]; 19 int mark[2010];//mark[i]表示 與 i 交配的昆蟲的編號！ 20 21 int getFather(int x){ 22 return x==f[x] ? x : f[x]=getFather(f[x]); 23 } 24 25 void Union(int a, int b){ 26 int fa=getFather(a), fb=getFather(b); 27 if(fa!=fb) 28 f[fa]=fb; 29 } 30 31 int main(){ 32 int t, cnt=0; 33 scanf("%d", &t); 34 while(t--){ 35 36 scanf("%d%d", &n, &m); 37 for(int i=1; i<=n; ++i) 38 f[i]=i; 39 memset(mark, 0, sizeof(mark)); 40 int flag=1; 41 while(m--){ 42 int u, v; 43 scanf("%d%d", &u, &v); 44 if(flag){ 45 if(getFather(u) == getFather(v)){ 46 flag=0; 47 continue; 48 } 49 if(!mark[u] && !mark[v]){ 50 mark[u]=v; 51 mark[v]=u; 52 } 53 else if(!mark[u]){ 54 mark[u]=v; 55 Union(u, mark[v]); //如果v配對了，u沒有配對，那么u和mark[v]就是同性昆蟲，放入集合之中 56 } 57 else if(!mark[v]){ 58 mark[v]=u; 59 Union(v,mark[u]);//,,,,,, 60 } 61 else{ 62 Union(u, mark[v]);//如果之前u和v都已經配對，現在u和v進行配對， 那么u和mark[v]是同性， v和mark[u]是同性！ 63 Union(v, mark[u]); 64 } 65 } 66 } 67 printf("Scenario #%d:\n",++cnt); 68 if (flag==1) 69 printf("No suspicious bugs found!\n"); 70 else 71 printf("Suspicious bugs found!\n"); 72 printf("\n"); 73 } 74 }
?
)
 強烈推薦!)
：logscape和logiq)
