[atcoder2306] rearranging (topology)

The question

It's on the blackboard n Number ,A First, according to their own wishes n Rearrange the numbers ( It can be the original order ), And then let B Do the following :
Select a pair of adjacent and coprime numbers , Exchange their positions .( This operation B It can be done countless times .)
A Want the dictionary order of this sequence to be as small as possible , and B Want the dictionary order of this sequence to be as large as possible .
When both of them adopt the optimal strategy , What does the resulting sequence look like .

Answer key

Discover non coprime numbers , Just at the beginning A When it's ready , The order is fixed , Can't change .
To minimize the lexicographic order , We count each number u, To the smallest number that has not been accessed and is not coprime with it v One side , Express u Guaranteed at v Before , To minimize the lexicographic order , It must be ensured that the penetration of each point is 1, Pictured

If you connect the edges like this , You can construct {3,2,4,6}

Obviously, it is better to connect the edges , To ensure the 2 It must be at the front

The implementation , Which numbers are not coprime with each number in the preprocessing , then dfs, For each number, edge to the smaller number first , Build a tree oriented graph . Then we use the priority queue to find the topological order with the largest dictionary order .

Code

#include<cstdio> #include<cstdlib> #include<vector> #include<queue> #include<algorithm> using namespace std; const int MAXN=2005; int gcd(int a,int b) {
      if(b==0) return a; return gcd(b,a%b); } int n,A[MAXN]; bool vis[MAXN]; vector<int> adj[MAXN],adj2[MAXN]; int deg[MAXN],ans[MAXN]; priority_queue<int> Q; void dfs(int u) {
      vis[u]=true; for(int i=0;i<(int)adj[u].size();i++) {
      int v=adj[u][i]; if(vis[v]) continue; adj2[u].push_back(v); deg[v]++; dfs(v); } } int main() {
      scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]); sort(A+1,A+n+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&gcd(A[i],A[j])>1) adj[i].push_back(j); for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); for(int i=1;i<=n;i++) if(deg[i]==0) Q.push(i); int it=0; while(!Q.empty()) {
      int u=Q.top(); ans[++it]=A[u]; Q.pop(); for(int i=0;i<(int)adj2[u].size();i++) {
      int v=adj2[u][i]; deg[v]--; if(deg[v]==0) Q.push(v); } } for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); return 0; }