| 确定大小 | ||||||
| ||||||
| Description | ||||||
| 现在有N个字母，（N <= 26），我们称之为A、B、C、D......。这次他们之间想确定大小关系。 但是现在只有一些残缺不全的关系，比如A > Z,然后没了...... 现在给出N个字母，（前N个大写字母），然后给出M个关系，每个关系只有大于和小于两种。 最后判断那些是可以确定他应有的大小位置的。 （没有给出的关系，均属于不可确定） | ||||||
| Input | ||||||
| 多组测试数据：每组测试数据： 第一行两个整数N，M。 接下来M行，每行一个关系，形式如：A>B A<B (M < 30) | ||||||
| Output | ||||||
| 按照ABCD...的顺序，输出可以确定的势力和他的排名。 如果都不可以确定，则输出-1。 | ||||||
| Sample Input | ||||||
| 3 2 A>B B>C 3 3 A>B B>C C>A | ||||||
| Sample Output | ||||||
| A 1 B 2 C 3 -1 | ||||||
| Source |
本题要求输出可以确定的人的排名2，首先需要建两个图，正向建一个反向建一个。
由于是有向图，对两个图中的每一个点进行bfs，记录以他为起始点所能扩展的点的数量
我的程序中用head和tail数组进行存储的。对于每个点，如何head值和tail值加起来的和为n-1
那么这个点的名次就是可以确定的了，
他的名次其实就是tail的值+1
还有一个问题就是结构体edge大小的问题
，我刚开始开的maxn，结果wa了，他的大小应该为2*maxn
#include<stdio.h> #include<iostream> #include<queue> #include<string.h> #include<algorithm> using namespace std; const int maxn=50; int head[maxn],tail[maxn]; int vis[maxn]; struct Edge{int to;int next; }edge1[maxn*4],edge2[maxn*4]; int head1[maxn]; int head2[maxn]; int tot1,tot2; int n,q; void addedge(int u,int v){edge1[tot1].to=v;edge1[tot1].next=head1[u];head1[u]=tot1++;edge2[tot2].to=u;edge2[tot2].next=head2[v];head2[v]=tot2++; } int head_num,tail_num; void head_bfs(int u){for(int i=1;i<=n;i++)vis[i]=0;vis[u]=1;queue<int>q;q.push(u);int v;while(!q.empty()){v=q.front();q.pop();for(int i=head1[v];i!=-1;i=edge1[i].next){if(!vis[edge1[i].to]){vis[edge1[i].to]=1;q.push(edge1[i].to);head_num++;}}} } void tail_bfs(int u){for(int i=1;i<=n;i++)vis[i]=0;vis[u]=1;queue<int>q;q.push(u);int v;while(!q.empty()){v=q.front();q.pop();for(int i=head2[v];i!=-1;i=edge2[i].next){if(!vis[edge2[i].to]){vis[edge2[i].to]=1;q.push(edge2[i].to);tail_num++;}}} } void init(){tot1=0;tot2=0;memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2)); } int main(){while(scanf("%d%d",&n,&q)!=EOF){init();char u,v,temp;getchar();int u1,v1;for(int i=1;i<=q;i++){scanf("%c%c%c",&u,&temp,&v);getchar();u1=u-'A'+1;v1=v-'A'+1;if(temp=='>')addedge(u1,v1);elseaddedge(v1,u1);}int cnt;for(int i=1;i<=n;i++){head_num=0;head_bfs(i);head[i]=head_num;tail_num=0;tail_bfs(i);tail[i]=tail_num;}bool flag=false;char c='A';for(int i=1;i<=n;i++){if(head[i]+tail[i]==n-1){printf("%c %d\n",c+i-1,tail[i]+1);flag=true;}}if(!flag)printf("-1\n");}return 0; }
