dfs暴力1,5,7WA求指导
查看原帖
dfs暴力1,5,7WA求指导
756660
B612Dusk楼主2023/5/17 20:53

dfs暴力的算法, 也就是建一个邻接表, 可以连在一起读的词语连一条边,dfs遍历时,每加入一个单词加上他的长度, 代码思路就是这样,请求大佬救助,不知道错在哪里了

#include<bits/stdc++.h>
#define N 10000
using namespace std;

int n, head[N], tot, vis[20], ans;
int fro[N], ed[N];//单词的首字母和尾字母
string s[N];
string t;

struct edges{
	int nxt, ver;
}edge[N];//边

inline void add(int a, int b){
	edge[++tot].ver = b;
	edge[tot].nxt = head[a];
	head[a] = tot;
}

void dfs(int x, int len){
	vis[x] = 1;
	ans = max(len , ans);
	for(int i = head[x]; i ;i = edge[i].nxt)
		if(!vis[edge[i].ver])	dfs(edge[i].ver , len + s[edge[i].ver].size());
}

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i ++){
		cin >> t;
		s[i] = t;
		fro[i] = s[i][0];
		ed[i] = s[i][s[i].size() - 1];
	}
	for(int i = 1;i <= n;i ++){
		for(int j = i + 1;j <= n;j ++){
			if(ed[i] == fro[j])
				add(i , j);
		}
	}
	for(int i = n;i >= 1;i --){
		for(int j = i - 1;j >= 1;j --)
			if(ed[i] == fro[j])
				add(i, j);
	}
	for(int i = 1;i <= n;i ++)	memset(vis , 0, sizeof vis) , dfs(i, s[i].size());
	printf("%d", ans);
	return 0;
} 
2023/5/17 20:53
加载中...