2015年2月5日 星期四

[CF 512A] Fox And Names

算基本的拓樸排序......但我第一次傳也沒注意到這種測資會悲劇XD :

2 ab a

出題者還很好心的在最後一個範測提示了這件事XD 而我是賽後寫的,不然比賽時應該會悲劇XD

code :

#include<bits/stdc++.h>
using namespace std;
vector<int> v[30] ;
 
char s[101][101] ;
int len[101] ;
 
int topo[30],t ;
int vis[30] ;
 
bool dfs(int x)
{
    vis[x]=-1 ;
    for(auto i : v[x])
    {
        if(vis[i]==-1) return 0 ;
        if(vis[i]==1) continue ;
        if(!dfs(i)) return 0 ;
    }
    vis[x]=1 ; topo[--t]=x ;
    return 1 ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%s",s[i]) , len[i]=strlen(s[i]) ;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
    {
        int k=0 ;
        for(;k<len[i]&&k<len[j]&&s[i][k]==s[j][k];k++) ;
        if(k!=len[i] && k==len[j])
            { printf("Impossible\n") ; return 0 ; }
        if(k==len[i]) continue ;
        v[s[i][k]-'a'].push_back(s[j][k]-'a') ;
    }
 
    for(int i=0;i<26;i++)
        sort(v[i].begin(),v[i].end()) ,
        v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin()) ;
 
    t=26 ;
    for(int i=0;i<26;i++) if(!vis[i])
    {
        if(!dfs(i)) { printf("Impossible\n") ; return 0 ; }
    }
 
    for(int i=0;i<26;i++) printf("%c",topo[i]+'a') ;
    printf("\n") ;
}
 

沒有留言:

張貼留言