| 确定大小 | ||||||
|
||||||
| 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); else addedge(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 ",c+i-1,tail[i]+1); flag=true; } } if(!flag) printf("-1 "); } return 0; }