【算法每日一练]-图论（保姆级教程 篇3（遍历））#图的遍历 #奶牛牧场 #杂务

今天讲图的遍历

目录

题目:图的遍历

思路：

题目：奶牛牧场

思路：  

题目：杂务

思路：

---

        

题目:图的遍历

        

思路：

         

正向建边需要跑O(N^2)会超时，所以反向建边，先从最大的点出发，能到的所有点都是最大点的值，然后更新下一个没有被更新过的点，
这样只需要O(n)就行，而且因为是从大到小遍历每个点，这样以来，每个点第一个更新的值便是最大值

        

#include 
#define N 100005
using namespace std;
int n,m,a[N];
vector <int>p[N];
void dfs(int x,int v){//从v点出发，可以到x点
	a[x]=v;     //所以这个x点能到的最大点就是v
	for(int i=0;isize();i++){
		if(!a[p[x][i]]) dfs(p[x][i],v);//如果这个p[x][i]点没有更新过，就用当前点的值进行更新
	}
}
int main(){
	cin>>n>>m;int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		p[v].push_back(u);//反向建边，箭头都逆向一下
	}
	for(int i=n;i>=0;i--){
		if(a[i]==0) dfs(i,i);//每个点都出发进行更新，被更新过的点不能再更新，否则一定会变小
	}
	for(int i=1;i<=n;i++){
		cout<' ';
	}
	return 0;
}

        

        

题目：奶牛牧场

        

思路：

不要奇怪，我写了bfs和dfs两种遍历方法，哪个都行

#include 
using namespace std;
const int K=105,N=1005;
int k,n,m,ans;
int a[K],cnt[N],vis[N];//cnt是能到此点的起点个数
vector<int>ve[N];
void dfs(int u){
	if(vis[u])return ;
	cnt[u]++;vis[u]=1;
	for(int i=0,sz=ve[u].size();i
		if(vis[ve[u][i]])continue;//注意这里是v[][]
		dfs(ve[u][i]);//个人认为vis=1放这里也可以
	}
}
void bfs(int u);
int main(){
	cin>>k>>n>>m;int x,y;
	for(int i=1;i<=k;i++)cin>>a[i];//保存每个奶牛的位置
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ve[x].push_back(y);
	}
	for(int i=1;i<=k;i++){
		memset(vis,0,sizeof(vis));
	//	dfs(a[i]);
		bfs(a[i]);
	}
	for(int i=1;i<=n;i++)	if(cnt[i]==k)ans++;
	cout<
}
 
 
void bfs(int u){
	queue<int>q;
	q.push(u);
	while(!q.empty()){
		int cur=q.front();q.pop();
		if(vis[cur])continue;
		vis[cur]=1;cnt[cur]++;
		for(int i=0,sz=ve[cur].size();i
			int v=ve[cur][i];
			if(vis[v])continue;
			q.push(v);
		}
	}
	
}
 
 

        

        

题目：杂务

        

思路：

         

注意到前驱任务可以并发执行，所以我们只需要完成最长前驱就行

直接topo排序就行，不过这里提供一种dfs的topo排序

vis[x]=max(vis[x],dfs(v[x][i])+tim[x]); 其实在树形dp的时候就已经见过一面的

        

#include  
#define N 10010
using namespace std;
vector <int> v[N];
int n,ans,tim[N],vis[N];//vis[x]存放完成任务x所需要的时间
int dfs(int x){
	if(vis[x]) return vis[x];   //枝剪
	for(int i=0;isize();i++){
		vis[x]=max(vis[x],dfs(v[x][i])+tim[x]);//递推公式
	}
	return vis[x];
}
int main(){
	cin>>n;int x,y;
	for(int i=1;i<=n;i++){
		cin>>x>>tim[x];//输入x，耗时tim[x]
		while(cin>>y&&y!=0){
			v[x].push_back(y);//正向建边，x的准备工作为y
		}
		if(v[x].size()==0)vis[x]=tim[x];
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,dfs(i));     //因为没有关系的两个任务可以并发执行
	}
	cout<
	
}