CF910C 拓扑排序求调
查看原帖
CF910C 拓扑排序求调
964817
Breath_of_the_Wild楼主2024/7/24 18:47

rt

#include<bits/stdc++.h>
using namespace std;
const int N=1003;
int n,deg[N];
string s[N];
vector<int> ans,g[N],g2[N];
queue<int> q;
bool Topo(){
	for(int i=0;i<26;i++){
		if(!deg[i]) q.push(i);
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		ans.push_back(x);
		for(int u:g[x]){
			deg[u]--;
			if(!deg[u]) q.push(u);
		}
	}
	return ans.size()==26;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(s[i][0]!=s[j][0]){
				g2[s[i][0]-'a'].push_back(s[j][0]-'a');
				continue;
			}
			if(s[i]==s[j]) continue;
			int p=0,mn=min(s[i].size(),s[j].size());
			while(p<mn){
				if(s[i][p]!=s[j][p]){
					g2[s[i][p]-'a'].push_back(s[j][p]-'a');
					break;
				}
				p++;
			}
		}
	}
	for(int i=0;i<26;i++){
		sort(g2[i].begin(),g2[i].end());
		if(g2[i].empty()) continue;
		g[i].push_back(g2[i][0]);
		deg[g2[i][0]]++;
		for(int j=1;j<g2[i].size();j++){
			if(g2[i][j]!=g2[i][j-1]){
				g[i].push_back(g2[i][j]);
				deg[g2[i][j]]++;
			}
		}
	}
	if(!Topo()) cout<<"Impossible";
	else{
		for(int u:ans){
			cout<<(char)(u+'a');
		}
	}
	return 0;
}
2024/7/24 18:47
加载中...