首页 > 代码库 > 51nod1076(tarjan)
51nod1076(tarjan)
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1076
题意:中文题诶~
思路:先用tarjan找出所有桥,再用桥限制的情况下dfs一遍。。。
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int MAXN=1e5+10; 5 vector<int> mp[MAXN]; 6 bool is_cut[MAXN]; 7 int n, m, ans=0; 8 int vis[MAXN]; 9 int low[MAXN], dfn[MAXN], pre[MAXN];//pre[u]记录u的父亲节点编号 10 //dfn[u]记录节点u在DFS过程中被遍历到的次序号,low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点(即DFS次序号最小 11 12 void tarjan(int u, int fu){ 13 pre[u]=fu;//记录当前u的父亲节点 14 dfn[u]=low[u]=++ans; 15 for(int i=0; i<mp[u].size(); i++){ 16 int v=mp[u][i]; 17 if(!dfn[v]){ 18 tarjan(v, u); 19 low[u]=min(low[u], low[v]); 20 }else if(fu!=v){//如果v是u的父亲的话,即有重边,那么不可能是桥 21 low[u]=min(low[u], dfn[v]); 22 } 23 } 24 } 25 26 void dfs(int x, int cnt){ 27 vis[x]=cnt; 28 for(int i=0; i<mp[x].size(); i++){ 29 int v=mp[x][i]; 30 if(vis[v]||is_cut[v]&&is_cut[x]) continue; 31 dfs(v, cnt); 32 } 33 } 34 35 void solve(void){ 36 for(int i=1; i<=n; i++){ 37 if(!dfn[i]) tarjan(i, 0); 38 int v=pre[i]; 39 if(dfn[v]<low[i]&&v>0){ 40 is_cut[i]=is_cut[v]=1; 41 } 42 } 43 int cnt=0; 44 for(int i=1; i<=n; i++){ 45 if(!vis[i]){ 46 cnt++; 47 dfs(i, cnt); 48 } 49 } 50 } 51 52 int main(void){ 53 scanf("%d%d", &n, &m); 54 for(int i=0; i<m; i++){ 55 int x, y; 56 scanf("%d%d", &x, &y); 57 mp[x].push_back(y); 58 mp[y].push_back(x); 59 } 60 solve(); 61 int q; 62 scanf("%d", &q); 63 while(q--){ 64 int s, e; 65 scanf("%d%d", &s, &e); 66 if(vis[s]==vis[e]) puts("Yes"); 67 else puts("No"); 68 } 69 return 0; 70 }
51nod1076(tarjan)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。