洛谷 P1656 炸铁路

你的名字 2023-07-13 03:46 6阅读 0赞

## 题目描述 ##

A 国派出将军uim，对 B 国进行战略性措施，以解救涂炭的生灵。

B 国有 nnn 个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。

uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 `key road`。

uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。

然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？

## 输入格式 ##

第一行 nnn，m(1≤n≤150m (1 \\leq n\\leq 150m(1≤n≤150，1≤m≤5000)1 \\leq m \\leq 5000)1≤m≤5000)，分别表示有 nnn 个城市，总共 mmm 条铁路。

以下 mmm 行,每行两个整数 a,ba, ba,b，表示城市 aaa 和城市 bbb 之间有铁路直接连接。

## 输出格式 ##

输出有若干行。

每行包含两个数字 aaa，b(a<b)b(a<b)b(a<b)，表示 <a,b><a,b><a,b> 是 `key road`。

请注意：输出时，所有的数对 <a,b><a,b><a,b> 必须按照 aaa 从小到大排序输出；如果aaa 相同，则根据 bbb 从小到大排序。

## 输入输出样例 ##

**输入 \#1**复制

6 6
    1 2
    2 3
    2 4
    3 5
    4 5
    5 6

**输出 \#1**复制

1 2
    5 6

**这是一道Tarjan算法求割边的题。重要的判断条件：if(low\[v\] > dfn\[u\])**

**这里还有一道涉及割点的题，较难，可以当练习做：[https://blog.csdn.net/qq\_36915686/article/details/104677266][https_blog.csdn.net_qq_36915686_article_details_104677266]**

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<deque> 
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 155; 
    
    //记录割边a---b 
    struct Node{
    	int a,b;
    	Node(int a,int b){
    		this->a = a;
    		this->b = b;
    	}
    };
    
    vector<Node> ans; //记录割边 
    vector<int> adj[MAXN]; //图的邻接表 
    int dfn[MAXN]; //dfn[u]=k 表示u节点在第k次Tarjan递归时被搜索到。 
    int low[MAXN]; //low[u]=k 表示u节点能追溯到的节点为k，从u节点出发能够到达k节点（dfn[k]尽量小） 
    int index;
    void Tarjan(int u,int parent){
    	dfn[u] = low[u] = index++;
    	for(int i=0;i<adj[u].size();i++){
    		int v = adj[u][i];
    		if(!dfn[v]){
    			Tarjan(v,u);
    			low[u] = min(low[u],low[v]);
    			if(low[v] > dfn[u]){  //判断割边的条件，除了u--v这条边之外，v到达不了u 
    				ans.push_back(Node(u,v));
    			}
    		}else if(v != parent){ //不能是从parent走到u再从u走到parent这样的两个节点之间的环。
    		// 如果两个节点之间有环的话，我们只考虑从父节点到子节点的边。不考虑从子节点到父节点的边。  
    			low[u] = min(low[u],dfn[v]);
    		}
    	}
    }
    
    void TravelTarjan(int n){
    	index = 1;
    	fill(dfn,dfn+n+1,0);
    	for(int i=1;i<=n;i++){
    		if(!dfn[i]){
    			Tarjan(i,i);	
    		}
    	}
    }
    
    bool cmp(const Node &node1,const Node &node2){
    	if(node1.a < node2.a){
    		return true;
    	}else if(node1.a == node2.a){
    		if(node1.b < node2.b){
    			return true;
    		}
    	}
    	return false;
    }
    
    int main(){
    	int n,m;
    	int u,v;
    	cin>>n>>m;
    	while(m--){
    		cin>>u>>v;
    		adj[u].push_back(v);
    		adj[v].push_back(u);
    	}
    	TravelTarjan(n);
    	sort(ans.begin(),ans.end(),cmp);
    	for(int i=0;i<ans.size();i++){
    		Node node = ans[i];
    		cout<<node.a<<" "<<node.b<<endl;
    	} 
    	return 0; 
    }

[https_blog.csdn.net_qq_36915686_article_details_104677266]: https://blog.csdn.net/qq_36915686/article/details/104677266