目录

L2-023 图着色问题 - dfs

测试点3：图可能是不联通的 所以不能是dfs(1)

L1-035 情人节 - 15

L1-039 古风排版 - 20

L1-040 最佳情侣身高差 - 10

L2-023 图着色问题 - dfs

PTA | 程序设计类实验辅助教学平台

思路：

从点1出发 进行dfs

dfs内 遍历和该点相连的其他点 如果颜色相同则返回false

主函数里遍历1~n的点 一旦有重复的就跳出

因为：图可能是不联通的，所以必须遍历1~n个点

如果1~n个点都满足不重复 则输出Yes 否则输出No

#include 
using namespace std;const int N=510;
int n,m,k;
bool g[N][N];
bool st[N];
int color[N];bool dfs(int u)
{st[u]=true;for(int i=1;i<=n;i++) //遍历该点相关联的节点if(g[u][i]){if(color[u]==color[i]) return false;if(!st[i])if(!dfs(i)) return false;}return true;
}int main()
{cin>>n>>m>>k;for(int i=0;i>a>>b;g[a][b]=g[b][a]=true;}int t;cin>>t;while(t--){sets;memset(color,0,sizeof color);memset(st,false,sizeof st);for(int i=1;i<=n;i++){cin>>color[i];s.insert(color[i]);}if(s.size()!=k){cout<<"No"<

#include 
using namespace std;const int N=510;
int n,m,k;
bool g[N][N];
bool st[N];
int color[N];bool dfs(int u)
{st[u]=true;for(int i=1;i<=n;i++) //遍历该点相关联的节点if(g[u][i]){if(color[u]==color[i]) return false;if(!st[i])if(!dfs(i)) return false;}return true;
}int main()
{cin>>n>>m>>k;for(int i=0;i>a>>b;g[a][b]=g[b][a]=true;}int t;cin>>t;while(t--){sets;memset(color,0,sizeof color);memset(st,false,sizeof st);for(int i=1;i<=n;i++){cin>>color[i];s.insert(color[i]);}if(s.size()!=k){cout<<"No"<

#include 
using namespace std;
int main()
{int cnt=0;string s,x2,x14;while(true){cin>>s;if(s==".") break;cnt++;if(cnt==2) x2=s;if(cnt==14) x14=s;}if(cnt<2) cout<<"Momo... No one is for you ...";else if(cnt<14) cout<

#include 
using namespace std;
int main()
{char ch[101][101];int n,t,m,cnt=0;cin>>n;cin.get();//接收回车 大坑string s;getline(cin,s);int l=s.size();for(int i=0;;i++)if((l+i)%n==0){t=i;break;}l+=t,m=l/n;for(int j=m-1;j>=0;j--)for(int i=0;i

#include 
using namespace std;
int main()
{int n;cin>>n;while(n--){char c;double h;cin>>c>>h;if(c=='M') printf("%.2f\n",h/1.09);else printf("%.2f\n",h*1.09);}
}