1021:
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std; #define N 10005
vector<int> v[N];
queue<int> q;
int tree[N],h[N],dis[N],vis[N];
int n,maxh; int findroot(int x){
if(tree[x]==-)
return x;
else{
int tmp=findroot(tree[x]);
tree[x]=tmp;
return tmp;
}
}
void merge(int x,int y){
x=findroot(x);
y=findroot(y);
if(x!=y){
tree[x]=y;
}
}
int bfs(int p){
int height=;;
int i,j,k;
while(!q.empty())
q.pop();
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
q.push(p);
vis[p]=;
while(!q.empty()){
k=q.front();
q.pop();
for(i=;i<v[k].size();i++){
if(!vis[v[k][i]]){
dis[v[k][i]]=dis[k]+;
if(height<dis[v[k][i]]) height=dis[v[k][i]];
q.push(v[k][i]);
vis[v[k][i]]=;
}
}
}
if(maxh<height)
maxh=height;
return height; }
int main(){
freopen("in2.txt","r",stdin);
int x,y;
int i,j;
scanf("%d",&n);
for(i=;i<N;i++)
tree[i]=-;
for(i=;i<n;i++){
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
merge(x,y);
}
int cnt=;
maxh=;
for(i=;i<=n;i++){
if(tree[i]==-)
cnt++;
}
if(cnt==){
for(i=;i<=n;i++){
h[i]=bfs(i);
}
for(i=;i<=n;i++){
if(h[i]==maxh)
printf("%d\n",i);
} }
else
printf("Error: %d components",cnt); return ;
}
对我来说挑战非常大的一道题，看了很多资料，看了很多方法，找到一个适合自己的代码，一直研究才弄的差不多。。
首先是利用并查集来判断连通分量的个数，这是一个很经典也很方便的方法，希望以后自己能多利用。非常好用，思路也不难。就是利用双亲表示法来表示树，把相关的合并在一起，然后递归找双亲节点，都是固定的东西。
然后就是bfs的东西，这个一直没接触过，第一次还是有很大的压力。各种各样的问题。希望以后再有深刻理解。其实思路并不难，关键是注意细节。
1022:
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
#define N 10005
struct book{
char id[];
char title[];
char author[];
char key[];
vector<string> keys;
char publish[];
char year[];
};
vector<book> v;
int n,m;
bool cmp(book a,book b){
if(strcmp(a.id,b.id)<)
return true;
else
return false;
}
void search(char *query){
int i,j;
char t[];
int r=,flag=;
memset(t,'\0',sizeof(t));
for(i=;i<strlen(query);i++)
t[i]=query[i+];
printf("%s\n",query);
for(i=;i<n;i++){
flag=;
switch(query[]){
case '': strcmp(t,v[i].title)==?flag=:r++; break;
case '': strcmp(t,v[i].author)==?flag=:r++; break;
case '': strcmp(t,v[i].publish)==?flag=:r++; break;
case '': strcmp(t,v[i].year)==?flag=:r++; break;
case '': {
for(j=;j<v[i].keys.size();j++){
t==v[i].keys[j]?flag=:r++;
}break;
}
} if(flag!=)
printf("%s\n",v[i].id); }
if(flag==&&r>=n)
printf("Not Found\n");
}
int main(){
freopen("in.txt","r",stdin);
int i=,j=,k=;
char temp[];
scanf("%d",&n);
getchar();
for(i=;i<n;i++){
struct book b;
gets(b.id);
gets(b.title);
gets(b.author);
while(cin>>temp){
b.keys.push_back(temp);
if(cin.get()=='\n')
break;
}
gets(b.publish);
gets(b.year);
v.push_back(b);
}
sort(v.begin(),v.end(),cmp); scanf("%d",&m);
getchar();
for(i=;i<m;i++){
char query[];
memset(query,'\0',sizeof(query));
gets(query);
search(query);
}
return ;
}
感觉有点伤到了。。本来不是复杂的问题，全都是关于输入的问题，然后是相同的项查找问题。。
c语言的输入字符串处理实在是能力有限，感觉受不了了。。排序也没有记清楚，这个记住吧。。然后是后来的相同项处理显得笨拙，还是别人的代码写的好一些。。
1023:
#include<stdio.h>
#include<string.h>
int x[];
int y[];
int main(){
long long n,m;
int i,j,t;
char a[],b[];
memset(x,,sizeof(y));
memset(y,,sizeof(y));
memset(a,'\0',sizeof(a));
memset(b,'\0',sizeof(b));
scanf("%s",a);
sscanf(a,"%lld",&n);
for(i=;i<strlen(a);i++){
t=a[i]-'';
x[t]++;
}
m=n*;
sprintf(b,"%lld",m);
for(i=;i<strlen(b);i++){
t=b[i]-'';
y[t]++;
}
int equal=;
for(i=;i<;i++){
if(x[i]!=y[i]){
equal=;
break;
}
}
if(equal==)
printf("No\n%s\n",b);
else{
printf("Yes\n%s\n",b);
}
}
挺简单的一道题，感觉自己全队的，就是有组过不了，不知道为什么，应该是字符串转数字的问题吧。。
思路没什么问题，我的方法貌似还简单一些。。