Description
This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307>.
There is a city in which Dixit lives. In the city, there are $ n $ houses. There is exactly one directed road between every pair of houses. For example, consider two houses A and B, then there is a directed road either from A to B or from B to A but not both. The number of roads leading to the $ i $ -th house is $ k_i $ .
Two houses A and B are bi-reachable if A is reachable from B and B is reachable from A. We say that house B is reachable from house A when there is a path from house A to house B.
Dixit wants to buy two houses in the city, that is, one for living and one for studying. Of course, he would like to travel from one house to another. So, he wants to find a pair of bi-reachable houses A and B. Among all such pairs, he wants to choose one with the maximum value of $ |k_A - k_B| $ , where $ k_i $ is the number of roads leading to the house $ i $ . If more than one optimal pair exists, any of them is suitable.
Since Dixit is busy preparing CodeCraft, can you help him find the desired pair of houses, or tell him that no such houses exist?
In the problem input, you are not given the direction of each road. You are given — for each house — only the number of incoming roads to that house ( $ k_i $ ).
You are allowed to ask only one type of query from the judge: give two houses A and B, and the judge answers whether B is reachable from A. There is no upper limit on the number of queries. But, you cannot ask more queries after the judge answers "Yes" to any of your queries. Also, you cannot ask the same query twice.
Once you have exhausted all your queries (or the judge responds "Yes" to any of your queries), your program must output its guess for the two houses and quit.
See the Interaction section below for more details.
Solution
因为原图是完全的有向图，所以缩点之后只会有一个源点和一个汇点
并且每一条边都指出一个点的拓扑序在另一个点前，所以缩点后拓扑序唯一
事实：两个点$u$，$v$在不同的SCC中，若$u$所在的SCC拓扑序较小，那么$u$的入度也较小
证明：对于不在这两个SCC中的点，连接这个点和$u$，$v$的边的方向是相同的，不影响两个点入度的相对大小
只考虑$u$和$v$所在的SCC，$u$的入度最大为$u$所在的SCC大小$-1$，$v$的入度最少为$u$所在的SCC大小
由上发现如果$u$的入度小于$v$，那么$u$的拓扑序一定小于$v$
枚举所有点对，按照入度之差排序，就相当于已经知道一个方向可以到达，只需要检查反方向是否可以到达即可
#include<algorithm> #include<iostream> #include<utility> #include<vector> #include<cstdio> using namespace std; int n,d[505]; char s[15]; vector<pair<int,pair<int,int> > >ve; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } int main(){ n=read(); for(int i=1;i<=n;i++)d[i]=read(); for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){ if(d[i]>d[j])ve.push_back(make_pair(d[i]-d[j],make_pair(i,j))); else ve.push_back(make_pair(d[j]-d[i],make_pair(j,i))); } sort(ve.rbegin(),ve.rend()); for(int i=0;i<ve.size();i++){ int a=ve[i].second.first,b=ve[i].second.second; printf("? %d %d ",a,b),fflush(stdout),scanf("%s",s+1); if(s[1]=='Y'&&s[2]=='e'&&s[3]=='s'){printf("! %d %d",a,b),fflush(stdout);return 0;} } printf("! 0 0 "),fflush(stdout); return 0; }