北京海华城市建设学校网站wordpress各版本下载地址

递归函数易错：

防止出现递归死循环！

题目

 题目：求诱导出的等价关系的关系矩阵

问题描述

给定有限集合上二元关系的关系矩阵，求由其诱导出的等价关系的关系矩阵。

输入格式

第一行输入n，表示矩阵为n阶方阵，第二行给出关系矩阵

输出格式

诱导出的等价关系的关系矩阵

样例输入

样例1；

3

1 0 0

0 0 0

0 0 1

样例2：

3

1 1 1

0 0 0

0 0 1

样例输出

样例1；

1 0 0

0 1 0

0 0 1

样例2：

1 1 1

1 1 1

1 1 1

 代码实现：

#include<bits/stdc++.h>
using namespace std;int main()
{int n; cin>>n;vector<vector<int>>graph(n, vector<int>(n, 0));	for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){//对称性int cur = graph[i][j]; if(cur == 1) cin>>cur; else cin>>graph[i][j];if(graph[i][j] == 1){graph[j][i] = 1;}//自反性if(i == j) graph[i][j] = 1;}}//传递性set<int>st;	auto dfs = [&](auto& dfs, int fa, int cur) -> void{for(int i=0; i<n; i++){if(cur != i && graph[cur][i] == 1){if(!st.count(i))//防止在两个关联项之间死循环递归{graph[fa][i] = 1;graph[i][fa] = 1;st.insert(i);dfs(dfs, fa, i);}}}		return;	};//调用递归时间	for(int i=0; i<n; i++){st.insert(i);dfs(dfs, i, i);st.clear();}//输出for(int i=0; i<n; i++){for(int j = 0; j < n; j++){cout<<graph[i][j]<<" ";}cout<<endl;}	return 0;
}