某個地區有n(n<=1000)個犯罪團伙，當地警方按照他們的危險程度由高到低給他們編號為1-n，他們有些團伙之間有直接聯系，但是任意兩個團伙都可以通過直接或間接的方式聯系，這樣這裡就形成了一個龐大的犯罪集團，犯罪集團的危險程度唯一由集團內的犯罪團伙數量確定，而與單個犯罪團伙的危險程度無關（該犯罪集團的危險程度為n）。現在當地警方希望花盡量少的時間（即打擊掉盡量少的團伙），使得龐大的犯罪集團分離成若干個較小的集團，並且他們中最大的一個的危險程度不超過n/2。為達到最好的效果，他們將按順序打擊掉編號1到k的犯罪團伙，請編程求出k的最小值。
輸入描述 Input Description第一行一個正整數n。接下來的n行每行有若干個正整數，第一個整數表示該行除第一個外還有多少個整數，若第i行存在正整數k，表示i，k兩個團伙可以直接聯系。
輸出描述 Output Description一個正整數，為k的最小值
樣例輸入 Sample Input 7
2 2 5
3 1 3 4
2 2 4
2 2 3
3 1 6 7
2 5 7
2 5 6
1
輸出1（打擊掉紅色團伙
數據范圍及提示 Data Size & Hintn<=1000
思路：逆向+分治
這樣退出來的一定是最小值
具體為什麼自己代入一組數據看看就全明白了
非語言能形容
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 struct node
6 {
7 int u;
8 int v;
9 int w;
10 int next;
11 }edge[10001];
12 int head[1001];
13 int num=1;
14 int map[1001][1001];
15 int vis[10001];
16 int tot;//記錄每次搜索時所能搜索到的點的數量
17 int n;
18 void add(int x,int y)
19 {
20 map[x][y]=1;
21 map[y][x]=1;
22 }
23 void dfs(int x)
24 {
25 vis[x]=1;
26 tot++;
27 for(int i=1;i<=n;i++)
28 {
29 if(map[x][i]==1&&vis[i]==0)
30 {
31 dfs(i);
32 }
33 }
34 }
35
36 int main()
37 {
38
39 scanf("%d",&n);
40 for(int i=1;i<=n;i++)
41 head[i]=-1;
42 for(int i=1;i<=n;i++)
43 {
44 int m;
45 scanf("%d",&m);
46 for(int j=1;j<=m;j++)
47 {
48 int p;
49 scanf("%d",&p);
50 edge[num].u=i;
51 edge[num].v=p;
52 //edge[num].w=p;
53 edge[num].next=head[i];
54 head[i]=num++;
55 }
56 }
57 /*for(int i=1;i<=n;i++)
58 {
59 int j=head[i];
60 while(j!=-1)
61 {
62 cout<<edge[j].v<<" ";
63 j=edge[j].next;
64 }
65 cout<<endl;
66 }
67 cout<<"********************************"<<endl;
68 for(int i=1;i<=n;i++)
69 {
70 cout<<edge[head[i]].v<<endl;
71 }*/
72 for(int i=n;i>=1;i--)
73 {
74 int j=head[i];
75 while(j!=-1)
76 {
77 if(edge[j].v>=i)
78 {
79 add(edge[j].v,i);
80 tot=0;
81 memset(vis,0,sizeof(vis));
82 dfs(i);
83 if(tot>n/2)
84 {
85 cout<<i;
86 return 0;
87 }
88 }
89 j=edge[j].next;
90 }
91 }
92 cout<<-1;
93 return 0;
94 }
