图论一般题合集

病毒溯源

题意：给定一棵树，求出最大深度，要求输出字典序最小的路径

Solution:由于看错题，以为是dag，然后发现只需要拓扑排序一下然后dp最长路就可以了。但值得注意的是需要提前对邻接表排序保证字典序，每次更新都需要维护终点，必须在过程中维护。我们找的是后缀最大值，但希望前缀结构最小。

vector<int>e[N];
int din[N];
vector<int>tp;
vector<int>dp(N+1,0);
void topsort(){
	queue<int>q;
	for(int i=0;i<=n-1;i++)if(din[i]==0){q.push(i);dp[i]=1;}
	while(q.size()){
		auto u=q.front();q.pop();
		tp.push_back(u);
		for(auto v:e[u]){
			din[v]--;
			if(din[v]==0)q.push(v);
		}
	}
}
//没仔细读题，以为是dag,结果是树
void solve(){
	cin>>n;
	for(int i=0;i<=n-1;i++){
		int num;cin>>num;
		for(int j=1;j<=num;j++){
			int x;cin>>x;
			din[x]++;
			e[i].push_back(x);
		}
	}
	for(int i=1;i<=n;i++)sort(e[i-1].begin(),e[i-1].end());
	topsort();
	//vector<int>dp(n+1,0);
	//提前维护终点
		int pos=0,len=0;
	vector<int>pre(n+1,-1);
	for(auto u:tp){
	//cerr<<u<<endl;

		for(auto v:e[u]){
			if(dp[v]<dp[u]+1){
				dp[v]=dp[u]+1;
				pre[v]=u;
			
			if(dp[v]>len){
				len=dp[v];
				pos=v;
			}
			}
			// else if(dp[v]==dp[u]+1){
				// if(pre[v]>u){
					// pre[v]=u;
				// }
			// }
		}
	}
//	cerr<<len<<endl;
	
	
	//找终点错误，这样无法保证答案字典序最小
	vector<int>ans;
	for(int i=pos;i!=-1;i=pre[i])ans.push_back(i);
	cout<<ans.size()<<endl;
for(int i=ans.size()-1;i>0;i--)cout<<ans[i]<<" ";
cout<<ans[0];
}

Solution:每当发现需要拓扑序dp的时候就应该想到记忆化搜索，如果发现是树可能想到的比较快。

vector<int>e[N];
int son[N];
bool st[N];
int dfs(int u){
	//cerr<<u<<endl;
	int res=0;
	for(auto v:e[u]){
		int rr=dfs(v);
		if(res<rr){
			res=rr;son[u]=v;
		}
		else if(res==rr){
			son[u]=min(son[u],v);
		}
	}
	//cerr<<u<<" "<<res<<endl;
	return res+1;
}
void solve(){
	cin>>n;
	for(int i=0;i<=n-1;i++){
		int num;cin>>num;
		for(int j=1;j<=num;j++){
			int x;cin>>x;
			e[i].push_back(x);
			st[x]=true;
		}
	}
	memset(son,-1,sizeof son);
	int root=0;
	while(st[root])root++;
	int ans=dfs(root);
	cout<<ans<<endl;
	cout<<root;
	for(int i=son[root];i!=-1;i=son[i])cout<<" "<<i;
}

送外卖https://www.acwing.com/problem/content/description/4477/

题意：给定一棵树，每次给点集加一个点，求从根出发到达当前点集所有点至少一次的最短总路程

Solution:对于这种每次都与上一次问题有细微变化的题目，我们考虑微观分析。然而我们发现依旧难以下手，因为我们的终点不确定，就完全没有确定的推理根基。。考虑对称性：加强题目条件，要求每次都要回到根。

按照加强题目的条件来考虑，对于当前点集的所有的点，我们最多走向他一次，离开一次，显然这样贪心是最优的，所有相关边最多会走两次，回到原问题我们需要钦定一个终点使得答案尽可能减少，选择深度最大的点即可。

实现方面：我们可以预处理所有点的深度，方便更新钦定终点，每次我们只需要对于新加进来的点考虑需要哪些新边，这些边只会走两次，以后就不用统计他们了，所以需要记忆化搜索，每次让新点向根跳，直到跳到已经统计过的边，考虑整个过程不难想到上面的边也已经统计过了。

int fa[N];
bool st[N];
int dep[N];
int mx=0,sum=0;
vector<int>e[N];
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;
	for(auto v:e[u]){
		dfs1(v,u);
	}
}
int root;
void dfs2(int u){
	if(u==root||st[u])return ;
	sum++;
	dfs2(fa[u]);
	st[u]=true;
}
void solve(){
	cin>>n>>m;
	//int root=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		fa[i]=x;
		if(x!=-1)e[x].push_back(i);
		if(x==-1)root=i;
	}
	dfs1(root,0);
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		mx=max(dep[x],mx);
		//cerr<<x<<" "<<dep[x]<<endl;
		dfs2(x);
		int ans=2*sum-mx+1;
		cout<<ans<<endl;
	}
}

千手观音https://www.acwing.com/activity/content/code/content/3586865/

题意：每个字符串代表一个数，连起来能够代表进制数，按大小顺序给出一些字符串组合起来的进制数,现在让你给这些字符串排序，如果存在不确定关系，字典序小的在前面。

Solution：首先明确这个关系具有传递性，可以证明，于是我们只需要相邻比较去建边.其次考虑两个位数不同的进制数是无法比较的（eg. 189和145.999）。我们只需要把能比较的第一位不同的建立边。用优先队列完成拓扑排序去满足字典序最小。

实现：我们需要哈希表去将字符串映射，用get函数将一个进制数的几个字符串全部拆成vector，便于我们处理，剩下的操作全都是基本图论。

debug:为了保证所有涉及到的字符串都会参与拓扑排序，我们需要在哈希表种创建他们。但是只创建一次，第二次再赋值为0会覆盖之前的入度信息。

unordered_map<string,int>din;
unordered_map<string,vector<string>>e;
vector<string>get(string s){
	vector<string>res;
	string word;
	for(auto x:s){
		if(x=='.'){
			res.push_back(word);	if(din.count(word)==0)din[word]=0;
			word="";
		}
		else word+=x;
	}
	//必须加判断条件，不然会丢失之前的入度信息
	if(din.count(word)==0)din[word]=0;//意义是所有点都能出现在未来topsort
	res.push_back(word);
  return res;
}
vector<string>tp;
void topsort(){
	//cerr<<endl;
	priority_queue<string,vector<string>,greater<string>>q;
	for(auto [x,y]:din)if(y==0)q.push(x);
	while(q.size()){
		auto u=q.top();q.pop();tp.push_back(u);
		
		for(auto v:e[u]){
			//cerr<<u<<" "<<v<<endl;
			din[v]--;
			if(din[v]==0)q.push(v);
		}
	}
}
void solve(){
	cin>>n;
	string str;
	cin>>str;
	auto last=get(str);
	for(int i=1;i<=n-1;i++){
		string s;cin>>s;
		auto cur=get(s);//当位数不同的时候无法进行比较。这里的.只是分割符，
		//不是小数点
		if(cur.size()==last.size()){
			for(int j=0;j<cur.size();j++){
				if(cur[j]!=last[j]){
					e[last[j]].push_back(cur[j]);
				//	cerr<<din["cn"]<<endl;
					//cerr<<i<<" "<<last[j]<<" "<<cur[j]<<endl;
					
					din[cur[j]]+=1;
					//cerr<<din["cn"]<<endl;
					break;
				}
			}
		}
		last=cur;
	}
	//cerr<<din["cn"]<<endl;
	topsort();
	cout<<tp[0];
	for(int i=1;i<tp.size();i++)cout<<"."<<tp[i];
}

给一颗基环树，请你输出所有环上的点。

Soluton1.考虑拓扑排序的思想，由于是无向图所以每个点至少出度为1，环上的点至少度为2，所以就只是偏移了入队标准，其他和拓扑排序一摸一样

vector<int>e[N];
int din[N];
void ts(){
	queue<int>q;
	for(int i=1;i<=n;i++)if(din[i]==1)q.push(i);
	while(q.size()){
		auto u=q.front();
		q.pop();
		for(auto v:e[u]){
			din[v]--;
			if(din[v]==1)q.push(v);
		}
	}
}
void solve(){
	cin>>n;
	DSU dsu(n+1);
	for(int i=1;i<=n;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
		din[v]++;din[u]++;
	}
	ts();
	for(int i=1;i<=n;i++)if(din[i]>1)cout<<i<<" ";
}

Solution2.考虑并查集找环，第一次合并失败的时候，必然这两个点都在环上。不加这个边，原图变成树，两个点之间的路径唯一，直接维护父节点一路倒退回去，或者对节点标记，再扫一遍。这里用set是偷懒了

vector<int>e[N];
int fa[N];

void solve(){
	cin>>n;
	DSU dsu(n+1);
	int l,r;
	for(int i=1;i<=n;i++){
		int u,v;cin>>u>>v;
		if(!dsu.merge(u,v)){l=u,r=v;continue;}
		e[u].push_back(v);
		e[v].push_back(u);
	}
	auto dfs=[&](auto self,int u,int f)->void{
		fa[u]=f;
		for(auto v:e[u]){
			if(v==f)continue;
			self(self,v,u);
		}
	};
	dfs(dfs,r,0);
	set<int>s;
	for(int j=l;j;j=fa[j])s.insert(j);
	for(auto x:s)cout<<x<<" ";
}