题解：CF2056B Find the Permutation

拓扑排序模板题。

用

p_i

与

p_j

的关系建图。如果

g_{i,j}=1

，那么连

i \to j

，否则连

j \to i

。然后拓扑排序。答案即为排序后的顺序。

CPP

void sol(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		deg[i]=0;
		p[i].clear();
		for (int j=1;j<=n;j++){
			char c;
			cin>>c;
			a[i][j]=c-'0';
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			if (a[i][j]) p[i].pb(j),deg[j]++;
			else p[j].pb(i),deg[i]++;
		}
	}
	queue<int> q;
	for (int i=1;i<=n;i++) if (!deg[i]) q.push(i);
	while (!q.empty()){
		int u=q.front();
		q.pop();
		cout<<u<<' ';
		for (int v:p[u]){
			if (!(--deg[v])) q.push(v);
		}
	}
	cout<<endl;
}

题解：CF2056B Find the Permutation

文章操作

相关推荐

评论

题解：CF2056B Find the Permutation