萌新求调代码,悬赏一关注哟!QwQ
查看原帖
萌新求调代码,悬赏一关注哟!QwQ
658786
STUDENT00楼主2022/12/17 15:21

码风良好的代码挂在这儿:

#include<bits/stdc++.h>
#define N 105
using namespace std;
int n,la[N],lb[N];
queue<pair<int,string> > Q;
bool vis[1<<26],flagg;
char a[N][26],b[N][26];
string empty;
void bfs(int p){
	int q=0;
	for(int i=0;i<la[p];i++){q|=(1<<a[p][i]-'A');}
	string qq=empty;qq[p]=1;
	Q.push(make_pair(q,qq));
	vis[q]=1;
	while(!Q.empty()){
		pair<int,string> now=Q.front();Q.pop();
		bool flag=1;
		for(int i=0;i<lb[p];i++){
			if(!((now.first>>b[p][i]-'A')&1)){flag=0;break;}
		}
		if(flag){
			flagg=1;
			printf("FD %d is redundant using FDs:",p+1);
			for(int i=0;i<n;i++){
				if(i!=p&&now.second[i]) printf(" %d",i+1);
			}
			printf("\n");
			return;
		}
		for(int i=0;i<n;i++){
			if(!now.second[i]){
				bool flag=1;
				for(int j=0;j<la[i];j++){
					if(!((now.first>>a[i][j]-'A')&1)){flag=0;break;}
				}
				if(flag){
					pair<int,string> ns=now;
					for(int j=0;j<lb[i];j++) ns.first|=(1<<b[i][j]-'A');
					if(vis[ns.first]) continue; 
					vis[ns.first]=1;
					ns.second[i]=1;
					Q.push(ns);
				}
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		char c=getchar();
		while(c<'A'||c>'Z') c=getchar();
		while(c!='-') a[i][la[i]++]=c,c=getchar();
		c=getchar();
		scanf("%s",b[i]);lb[i]=strlen(b[i]);
	}
	for(int i=0;i<n;i++) empty+=char(0);
	for(int i=0;i<n;i++){
		memset(vis,0,sizeof(vis));
		bfs(i);
	}
	if(!flagg) printf("No redundant FDs.");
	return 0;
}
2022/12/17 15:21
加载中...