poj 1419(図のシェーディング問題、検索)
8857 ワード
タイトルリンク:http://poj.org/problem?id=1419
考え方:データが弱いだけだ!直接爆捜して、順番に検索すればいいです.
View Code
考え方:データが弱いだけだ!直接爆捜して、順番に検索すればいいです.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6 using namespace std;
7
8 int n,m,max_num;
9 vector<vector<int> >G;
10
11 int color[111];
12 int ans[111];
13
14 void dfs(int num,int count)
15 {
16 if(num==n+1){
17 if(count>max_num){
18 max_num=count;
19 int cnt=0;
20 for(int i=1;i<=n;i++){
21 if(color[i])ans[cnt++]=i;
22 }
23 }
24 return ;
25 }
26 bool flag=true;
27 for(int i=0;i<G[num].size();i++){
28 if(color[G[num][i]])flag=false;
29 }
30 if(flag){
31 color[num]=1;
32 dfs(num+1,count+1);
33 color[num]=0;
34 }
35 dfs(num+1,count);
36 }
37
38 int main()
39 {
40 int _case,u,v;
41 scanf("%d",&_case);
42 while(_case--){
43 scanf("%d%d",&n,&m);
44 G.clear();
45 G.resize(n+2);
46 while(m--){
47 scanf("%d%d",&u,&v);
48 G[u].push_back(v);
49 G[v].push_back(u);
50 }
51 memset(color,0,sizeof(color));
52 max_num=0;
53 dfs(1,0);
54 printf("%d
",max_num);
55 for(int i=0;i<max_num;i++){
56 printf(i?" %d":"%d",ans[i]);
57 }
58 puts("");
59 }
60 return 0;
61 }
View Code