分析:
感觉和AGC001的一道题很像啊。。。
仍然是把矛盾关系连边，有边相连的点相对位置不会改变。
然后因为这题是无向边，所以可以在每个联通块中，从最小的一个点出发，依次遍历尽量小的位置，得到的序列即为这个联通块的序列。然后多个联通块每次取出队首最大的一个即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 2010
using namespace std;
typedef long long ll;
int n,cnt[MAXN];
ll a[MAXN];
vector<int> b[MAXN],c[MAXN];
priority_queue<pair<ll,int> > qx;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);
}
int d[MAXN];
bool vis[MAXN];
void dfs(int x){vis[x]=1;for(int i=0;i<int(b[x].size());i++)if(vis[b[x][i]]==0){c[x].push_back(b[x][i]);d[b[x][i]]++;dfs(b[x][i]);}
}
priority_queue<pair<ll,int> > q;
int main(){//freopen("newgame.in","r",stdin);//freopen("newgame.out","w",stdout);SF("%d",&n);for(int i=1;i<=n;i++)SF("%lld",&a[i]);sort(a+1,a+1+n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j&&gcd(a[i],a[j])!=1ll)b[i].push_back(j);for(int i=1;i<=n;i++)if(vis[i]==0)dfs(i);for(int i=1;i<=n;i++)if(d[i]==0)q.push(make_pair(a[i],i));while(!q.empty()){PF("%lld ",q.top().first); int x=q.top().second;q.pop();for(int i=0;i<int(c[x].size());i++){d[c[x][i]]--;if(d[c[x][i]]==0)q.push(make_pair(a[c[x][i]],c[x][i]));}}
}