没有环为什么会T啊
查看原帖
没有环为什么会T啊
181308
小又又楼主2021/6/27 09:49
void dfs2(int x){
	if (vis[x]) return;
	vis[x] = 1;
	for (int i = 0;i <= 1;i++){
		if (sam.ch[x][i]){
	//		cout<<sam.ch[x][i]<<endl;
			if (dp[sam.ch[x][i]] > 1) printf("%d\n",dp[sam.ch[x][i]]);	
			dfs2(sam.ch[x][i]);
		}
	}
	vis[x] = 0;
}

这里不加vis记录就会T,底下是完整代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define B cout<<"Breakpoint"<<endl;
#define O(x) cout<<#x<<" "<<x<<endl;
#define o(x) cout<<#x<<" "<<x<<" ";
using namespace std;
int read(){
	int x = 1,a = 0;char ch = getchar();
	while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
	while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
	return x*a;
}
const int maxn = 6005;
int dp[maxn];
struct SAM{
	int len[maxn],ch[maxn][30],fa[maxn];
	int tot,lastNode;
	SAM(){tot = lastNode = 1;}
	void add(int c){
		int preNode = lastNode;
		int nowNode = lastNode = ++tot;
		dp[nowNode] = 1,len[nowNode] = len[preNode]+1;
		for (;preNode&&!ch[preNode][c];preNode = fa[preNode]) ch[preNode][c] = nowNode;
		if (!preNode) fa[nowNode] = 1;
		else{
			int tmpNode = ch[preNode][c];
			if (len[tmpNode] == len[preNode]+1) fa[nowNode] = tmpNode;
			else{
				int tmpNode1 = ++tot;
				len[tmpNode1] = len[tmpNode],fa[tmpNode1] = fa[tmpNode];
				for (int i = 0;i <= 1;i++) ch[tmpNode1][i] = ch[tmpNode][i];
				len[tmpNode1] = len[preNode]+1;
				fa[tmpNode] = fa[nowNode] = tmpNode1;
				for (;preNode&&ch[preNode][c] == tmpNode;preNode = fa[preNode]) ch[preNode][c] = tmpNode1;
			}
		}
	}
	
}sam;
struct node{
	int to[maxn],nxt[maxn],head[maxn],tot;
	node(){tot = 0;memset(head,0,sizeof(head));}
	void add(int u,int v){
		to[++tot] = v,nxt[tot] = head[u],head[u] = tot;
	}
}ed1,ed2;
int n;
void dfs(int x){
	for (int i = ed1.head[x];i;i = ed1.nxt[i]){
		int to = ed1.to[i];
		dfs(to);
		dp[x] += dp[to];
	}
}
bool vis[maxn];
void dfs2(int x){
	if (vis[x]) return;
	vis[x] = 1;
	for (int i = 0;i <= 1;i++){
		if (sam.ch[x][i]){
	//		cout<<sam.ch[x][i]<<endl;
			if (dp[sam.ch[x][i]] > 1) printf("%d\n",dp[sam.ch[x][i]]);	
			dfs2(sam.ch[x][i]);
		}
	}
	vis[x] = 0;
}
char s[maxn];
int main(){
	n = read();
	scanf ("%s",s+1);
	for (int i = 1;i <= n;i++) sam.add(s[i]-'0');
	for (int i = 1;i <= sam.tot;i++) ed1.add(sam.fa[i],i);
	dfs(1),dfs2(1);
	return 0;
}
2021/6/27 09:49
加载中...