HDU1213
http://acm.hdu.edu.cn/showproblem.php?pid=1213
問題描述
今天是伊格納修斯的生日。他邀請了很多朋友。現在是晚餐時間。伊格納修斯想知道他至少需要多少桌子。你必須注意到并非所有的朋友都互相認識，而且所有的朋友都不想和陌生人呆在一起。
這個問題的一個重要規則是，如果我告訴你A知道B，B知道C，那意味著A，B，C彼此了解，所以他們可以留在一個表中。
例如：如果我告訴你A知道B，B知道C，D知道E，所以A，B，C可以留在一個表中，D，E必須留在另一個表中。所以Ignatius至少需要2張桌子。
輸入
輸入以整數T（1 <= T <= 25）開始，表示測試用例的數量。然后是T測試案例。每個測試用例以兩個整數N和M開始（1 <= N，M <= 1000）。N表示朋友的數量，朋友從1到N標記。然后M行跟隨。每一行由兩個整數A和B（A！= B）組成，這意味著朋友A和朋友B彼此了解。兩個案例之間會有一個空白行。
?
對于每個測試用例，只輸出Ignatius至少需要多少個表。不要打印任何空白。
樣本輸入
2
5 3
1 2
2 3
4 5
?
5 1
2 5
樣本輸出
2
4
并查集基礎題
#include<cstdio>
#include<iostream>
using namespace std;
int fa[1005];
int n,m;
void init()//初始化
{for(int i=0;i<1005;i++)fa[i]=i;
}
int find(int x)//尋根
{if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];
}
void union(int x,int y)//判斷、合并
{int a=find(x),b=find(y);if(a!=b)fa[b]=a;
}
int main()
{int t;scanf("%d",&t);while(t--){int a,b,cnt=0;scanf("%d%d",&n,&m);init();for(int i=1;i<=m;i++)//合并{scanf("%d%d",&a,&b);union(a,b);}for(int i=1;i<=n;i++)//統計{find(i);if(find(i)==i)cnt++;}printf("%d\n",cnt);}return 0;
}
POJ1611
http://poj.org/problem?id=1611
描述
嚴重急性呼吸系統綜合癥（SARS）是一種病因不明的非典型肺炎，在2003年3月中旬被認為是一種全球性威脅。為了盡量減少對他人的傳播，最好的策略是將嫌疑人與其他嫌疑人分開。?
在Not-Spreading-Your-Sickness University（NSYSU），有許多學生團體。同一組中的學生經常互相交流，學生可以加入幾個小組。為了防止可能的SARS傳播，NSYSU收集所有學生組的成員列表，并在其標準操作程序（SOP）中制定以下規則。?
一旦組中的成員是嫌疑人，該組中的所有成員都是嫌疑人。?
然而，他們發現，當學生被認定為嫌疑人時，識別所有嫌疑人并不容易。你的工作是編寫一個找到所有嫌疑人的程序。
輸入
輸入文件包含幾種情況。每個測試用例以一行中的兩個整數n和m開始，其中n是學生數，m是組的數量。您可以假設0 <n <= 30000且0 <= m <= 500.每個學生都使用0到n-1之間的唯一整數進行編號，并且最初學生0在所有情況下都被識別為嫌疑人。該行后面是組的m個成員列表，每組一行。每行以整數k開頭，表示組中的成員數。在成員數量之后，有k個整數代表該組中的學生。一行中的所有整數由至少一個空格分隔。?
n = 0且m = 0的情況表示輸入結束，無需處理。
?
對于每種情況，輸出一行中的嫌疑人數量。
樣本輸入
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0樣本輸出
4
1
1?
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <string>
using namespace std;
int a[30001],pre[30001];
int find(int x)//尋根
{if(pre[x]==x)return x;elsereturn pre[x]=find(pre[x]);
}
void union(int x, int y)//合并
{int fx = find(x), fy = find(y);if (fx != fy)pre[fy] = fx;
}int main()
{int n,m;while (scanf("%d%d", &n, &m) != EOF && (n || m)){int sum = 0;for (int i = 0; i < n; i++)//初始化pre[i] = i;for (int i = 0; i < m; i++){int k;scanf("%d", &k);if (k >= 1){scanf("%d", &a[0]);for (int j = 1; j < k; j++){scanf("%d", &a[j]);//接收union(a[0], a[j]);//和0號一組}}}for (int i = 0; i < n; i++)//統計if (find(i) ==pre[0])sum++;printf("%d\n", sum);}return 0;
}
?POJ2236
http://poj.org/problem?id=2236
描述
地震發生在東南亞。ACM（亞洲合作醫療團隊）已經與膝上電腦建立了無線網絡，但是一次意外的余震襲擊，網絡中的所有計算機都被打破了。計算機一個接一個地修復，網絡逐漸開始工作。由于硬件限制，每臺計算機只能直接與距離它不遠的計算機進行通信。但是，每臺計算機都可以被視為兩臺計算機之間通信的中介，也就是說，如果計算機A和計算機B可以直接通信，或者計算機C可以與A和A進行通信，則計算機A和計算機B可以進行通信。 B.?
在修復網絡的過程中，工作人員可以隨時進行兩種操作，修復計算機或測試兩臺計算機是否可以通信。你的工作是回答所有的測試操作。?
輸入
第一行包含兩個整數N和d（1 <= N <= 1001,0 <= d <= 20000）。這里N是計算機的數量，編號從1到N，D是兩臺計算機可以直接通信的最大距離。在接下來的N行中，每行包含兩個整數xi，yi（0 <= xi，yi <= 10000），這是N臺計算機的坐標。從第（N + 1）行到輸入結束，有一些操作，這些操作是一個接一個地執行的。每行包含以下兩種格式之一的操作：?
1。“O p”（1 <= p <= N），表示修復計算機p。?
2.“S p q”（1 <= p，q <= N），這意味著測試計算機p和q是否可以通信。?
輸入不會超過300000行。?
產量
對于每個測試操作，如果兩臺計算機可以通信則打印“SUCCESS”，否則打印“FAIL”。
樣本輸入
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4樣本輸出
FAIL
SUCCESS?思路：對每次修好的電腦對其它已經修好的電腦遍歷，如果距離小于等于最大通信距離就將他們合并。
注意：
1、坐標之后給出的計算機編號都是n+1的。例如O 3，他實際上修理的是編號為2的計算機，因為計算機是從0開始編號的。
2、比較距離的時候注意要用浮點數比較，否則會WA。
3、"FAIL"不要寫成"FALL"。
4、字符串輸入的時候注意處理好回車，空格等情況。
5、注意N的范圍（1 <= N <= 1001），最大是1001，不是1000。是個小坑，數組開小了可能會錯哦。
?
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;#define MAXN 1010int dx[MAXN],dy[MAXN]; //坐標
int par[MAXN]; //x的父節點
int repair[MAXN] ={0};
int n;void Init()//初始化
{int i;for(i=0;i<=n;i++)par[i] = i;
}int Find(int x)//尋根
{if(par[x]!=x)par[x] = Find(par[x]);return par[x];
}void Union(int x,int y)//合并
{par[Find(x)] = Find(y);
}int Abs(int n)//絕對值
{return n>0?n:-n;
}double Dis(int a,int b)//坐標
{return sqrt( double(dx[a]-dx[b])*(dx[a]-dx[b]) + (dy[a]-dy[b])*(dy[a]-dy[b]) );
}int main()
{int d,i;//初始化scanf("%d%d",&n,&d);Init();//輸入坐標for(i=0;i<n;i++){scanf("%d%d",&dx[i],&dy[i]);}//操作char cmd[2];int p,q,len=0;while(scanf("%s",cmd)!=EOF){switch(cmd[0]){case 'O':scanf("%d",&p);p--;repair[len++] = p;for(i=0;i<len-1;i++) //遍歷所有修過的計算機，看能否聯通if( repair[i]!=p && Dis(repair[i],p)<=double(d) )Union(repair[i],p);break;case 'S':scanf("%d%d",&p,&q);p--,q--;if(Find(p)==Find(q)) //判斷printf("SUCCESS\n");else printf("FAIL\n");default:break;}}return 0;
}?
