蓝桥杯 2017 决赛 发现环 (求环内的点)

本文主要是介绍蓝桥杯 2017 决赛 发现环 (求环内的点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

方法一：dfs

#include<stdio.h>
#include<string.h>
#include<vector> 
#include<stack>
using namespace std;
const int N = 100000+5;
int n;
bool vis[N];
vector<int> adj[N];
bool in_stack[N];
bool flag[N];
stack<int> s;void dfs(int cur,int fa){vis[cur] = true;s.push(cur);in_stack[cur] = true;for(int i = 0; i < adj[cur].size(); ++i){int v = adj[cur][i];if(!vis[v]){dfs(v,cur);}else if(in_stack[v] && fa != v){//不能是父节点int u;do{u = s.top();flag[u] = true;s.pop();}while(u != v);//return;  // 不知道为啥 不能 直接return; break;}}	if(!s.empty()) //这里如果不判断 直接出栈 会RE  从 100 -> 0 悲剧 s.pop();in_stack[cur] = false;	//出栈了必须标记 }int main(){scanf("%d",&n);int a,b;for(int i = 0; i < n; ++i){scanf("%d%d",&a,&b);adj[a].push_back(b);adj[b].push_back(a);}dfs(1,1); //图一定连通 所以 从一个点搜索就OK了 
//		for(int i = 1; i <= n; ++i){
//			if(!vis[i]){
//				dfs(i,i);
//			}
//		}for(int i = 1; i <= n; ++i){if(flag[i]){printf("%d ",i);}}return 0;}

#include<stdio.h>
#include<string.h>
#include<vector> 
#include<stack>
#include<algorithm>
using namespace std;
const int N = 100000+5;
int n;
bool vis[N];
vector<int> adj[N];
bool in_stack[N];
bool flag[N];
stack<int> s;
int index;
int low[N];
int dfn[N];
int color;
vector<int> cop[N];//记录每个连通分量 其实只有一个 void dfs(int cur,int fa){dfn[cur] = low[cur] = ++index;vis[cur] = true;s.push(cur);in_stack[cur] = true;for(int i = 0; i < adj[cur].size(); ++i){int v = adj[cur][i];if(!vis[v]){dfs(v,cur);low[cur] = min(low[cur],low[v]);}else if(in_stack[v] && v != fa){ //这是关键 不能是父节点 类似于判断割点 low[cur] = min(low[cur],dfn[v]);}}in_stack[cur] = false;if(low[cur] == dfn[cur]){ //说明是个连通分量 int u;++color;do{u = s.top();cop[color].push_back(u);s.pop();}while(u != cur);}	}int main(){scanf("%d",&n);int a,b;for(int i = 0; i < n; ++i){scanf("%d%d",&a,&b);adj[a].push_back(b);adj[b].push_back(a);}dfs(1,1); //图一定连通 所以 从一个点搜索就OK了 for(int i = 0; i < N; ++i){if(cop[i].size() > 1){for(int j = 0; j < cop[i].size(); ++j){sort(cop[i].begin(),cop[i].end());//排序 printf("%d ",cop[i][j]);}}}return 0;}

这篇关于蓝桥杯 2017 决赛 发现环 (求环内的点)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---