下面是PTA的OJ平台
题解
L2-023 图着色问题
图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
输入格式：
输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。
输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。
输入样例：
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4
输出样例：
Yes
Yes
No
No
AC代码：
#include<bits/stdc++.h> using namespace std; const int N=1e8+10; struct node{ int u,v; }p[N]; int main() { int v,e,k; cin>>v>>e>>k; int a[501]; set<int>st; for(int i=0;i<e;i++) cin>>p[i].u>>p[i].v; int q; cin>>q; while(q--) { for(int i=1;i<=v;i++) { cin>>a[i]; st.insert(a[i]); } if(st.size()!=k) { cout<<"No"<<endl; st.clear(); continue; } int flag=0; for(int i=0;i<e;i++) { if(a[p[i].u]==a[p[i].v]) { flag=1; break; } } if(flag) cout<<"No"<<endl; else cout<<"Yes"<<endl; st.clear(); } }
L2-024 部落
在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数N（≤10
4
），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ⋯ P[K]
其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10
4
。
之后一行给出一个非负整数Q（≤10
4
），是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例：
10 2
Y
N
AC代码：
#include<bits/stdc++.h> using namespace std; int fa[10005]; int find(int i) { if(fa[i]==i) return i; else { fa[i]=find(fa[i]); return fa[i]; } } int unio(int i,int j) { int x=find(i); int y=find(j); fa[x]=y; } int main() { int n; cin>>n; for(int i=1;i<=10005;i++) fa[i]=i; set<int>st; for(int i=1;i<=n;i++) { int k,x,x1; cin>>k; cin>>x; st.insert(x); for(int j=1;j<k;j++) { cin>>x1; st.insert(x1); unio(x,x1); } } int ans=0; for(int i=1;i<=st.size();i++) { if(fa[i]==i) ans++; } cout<<st.size()<<" "<<ans<<endl; int m; cin>>m; for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; if(find(a)==find(b)) cout<<"Y"<<endl; else cout<<"N"<<endl; } }
L2-025 分而治之
分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
输入格式：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。
输出格式：
对每一套方案，如果可行就输出YES，否则输出NO。
输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
输出样例：
NO
YES
YES
NO
NO
AC代码：
#include<bits/stdc++.h> using namespace std; int n,m,a,b,k,dt[10010]; vector<int>v[10010]; bool isleagle(int n) { for(int i=1;i<=n;i++) { for(int j=0;j<v[i].size();j++) { if(dt[i]==0&&dt[v[i][j]]==0) return false; } } return true; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } int t; scanf("%d",&t); for(int i=0;i<t;i++) { memset(dt,0,sizeof(dt)); scanf("%d",&k); for(int j=0;j<k;j++) { scanf("%d",&a); dt[a]=1; } if(isleagle(n)==true) printf("YES\n"); else printf("NO\n"); } }
L2-026 小字辈
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9
2 6 5 5 -1 5 6 4 7
输出样例：
4
1 9
AC代码：
#include<bits/stdc++.h> using namespace std; int f[100001]={-1}; int h[100001]; int find(int x) { if(f[x]==-1) h[x]=1; else if(h[x]==0) h[x]=find(f[x])+1; return h[x]; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>f[i]; for(int i=1;i<=n;i++) find(i); int maxn=0; for(int i=1;i<=n;i++) { if(h[i]>maxn) maxn=h[i]; } cout<<maxn<<endl; bool flag=true; for(int i=1;i<=n;i++) { if(h[i]==maxn) { if(flag) { flag=false; cout<<i; } else cout<<" "<<i; } } }
4
写在最后
🍉🍉🍉不必偏执于未知的真实，身处的当下即是意义和真实，爱才是解题的答案，也是刻画人生色彩的笔尖，耐心的走下去，总会遇到你爱的人和爱你的人。
🍁🍁🍁好啦，本文的内容就到此结束啦，我们下期再见哦！另外在祝各位小伙伴们要天天开心哦！
🍂🍂🍂如果你觉得本文对你有帮助的话，还请不要吝惜您的三连哦！您的支持就是我创作的最大动力！！爱你们💕💕💕
