搜索应用小结

void check(int u){
	use[u]=1;
	for(int i:g[u]){
		if(use[i]==1){
			f=1;
			return ;
		}
		if(use[i]==0)check(i);
	}
	use[u]=2;
}

bool check(){
	for(int i=0;i<n;i++){
		rd[i]=0;
		g[i].clear();
	}
	for(int i=1;i<=m;i++){
		g[u[i]].push_back(v[i]);
		rd[v[i]]++;
	}
	queue<int>q;
	int cnt=0;
	for(int i=0;i<n;i++){
		if(rd[i]==0)q.push(i),cnt++;
	}
	while(!q.empty()){
		int pos=q.front();
		q.pop();
		for(int i:g[pos]){
			if(--rd[i]==0)q.push(i),cnt++;
		}
	}
	if(cnt!=n)return 0;
	else return 1;
}

bool spfa() {
	for(int i=1;i<=n;i++){
		q.push(i);
		vis[i]=true;
	}
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		vis[x]=0; 
		for(pii i:g[x]) { 
			if(dis[i.first]>dis[x]+i.second){
				dis[i.first]=dis[x]+i.second;
				cnt[i.first]=cnt[x]+1;
				if(cnt[i.first]>=n)return true;
				if(!vis[i.first]){ 
					vis[i.first]=1; 
					q.push(i.first);
				}
			}
		}
	}
	return false;
}