Submission #1694580

---

Source Code Expand

//dfs树的灵活运用
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 2010
#define inf 2147483647
using namespace std;

struct edge{int x, y, next;}a[4010010];
int n, w[N], l, p[N], flag[N], fa[N], S, mnp, b[N], du[N], ans[N];
vector<int>son[N], son1[N];

inline int gcd(int a, int b){return b?gcd(b, a%b):a;}
inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=p[x]; p[x]=l;}

inline void dfs(int x){
	flag[x]=1; son1[x].clear();
	for(int i=p[x]; i; i=a[i].next)if(!flag[a[i].y])son1[x].push_back(a[i].y);
	int mnp; w[0]=inf;
	while(1){
		mnp=0;
		for(int i=0; i<son1[x].size(); i++)if(!flag[son1[x][i]]&&w[mnp]>w[son1[x][i]])mnp=son1[x][i];
		if(!mnp)break;
		fa[mnp]=x; dfs(mnp);
	}
}

inline void solve(){
	l=0; memset(p, 0, sizeof(p)); memset(du, 0, sizeof(du));
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)if(gcd(b[i], b[j])!=1){add(i, j); du[j]++;}
	memset(flag, 0, sizeof(flag));
	for(int i=1; i<=n; i++)if(!du[i])flag[i]=1;
	int mnp; b[0]=-inf;
	for(int i=1; i<=n; i++){
		mnp=0;
		for(int j=1; j<=n; j++)if(flag[j]&&b[mnp]<b[j])mnp=j;
		ans[i]=b[mnp]; flag[mnp]=0;
		for(int j=p[mnp]; j; j=a[j].next){du[a[j].y]--; if(!du[a[j].y])flag[a[j].y]=1;}
	}
}

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++)scanf("%d", &w[i]);
	S=n+1; w[n+1]=0;
	l=0; memset(p, 0, sizeof(p));
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)if(gcd(w[i], w[j])!=1){add(i, j); add(j, i);}
	for(int i=1; i<=n; i++){add(S, i); add(i, S);}
	memset(flag, 0, sizeof(flag));
	fa[S]=0; dfs(S);
	for(int i=1; i<=S; i++)son[i].clear();
	for(int i=1; i<=n; i++)son[fa[i]].push_back(i);
	memset(flag, 0, sizeof(flag)); flag[S]=1; l=-1;
	for(int i=1; i<=S; i++){
		mnp=0; w[0]=inf;
		for(int j=1; j<=S; j++)if(flag[j]&&w[mnp]>w[j])mnp=j;
		b[++l]=w[mnp]; flag[mnp]=0;
		for(int j=0; j<son[mnp].size(); j++)flag[son[mnp][j]]=1;
	}
	solve();
	for(int i=1; i<=n-1; i++)printf("%d ", ans[i]); printf("%d", ans[n]);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:46:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++)scanf("%d", &w[i]);
                                           ^

Judge Result