Wyszukiwanie mostów w grafie

Wyszukiwanie mostów w grafie

Most w grafie to taka krawędź, która po usunięciu spowoduje, że graf zostnie podzielony na dwa rozłączne grafy.

Zarys algorytmu

• W pierwszej części algorytmu puszczamy DFS'a, aby ponumerował nam wierzchołki niezależnie od nadanych im numerów, zgodnie z kolejnością ich odwiedzania. Taki sam numer przypisujemy do wartości low. Podczas odwiedzania wierzchołków zapamiętujęmy informację o jego ojcu (wierzchołku, z którego przyszliśmy).
• W kolejnym kroku stosujemy ponownie DFS'a analizując kolejne wierzchołki przetworzone (czyli takie, do których więcej już nie będziemy wracać) w następujący sposób:
  • wybieramy wszystkie połączenia oprócz połączenia ze swoim ojcem, i ustalamy wartość low na najmniejszą ze wszystkich sąsiadów oraz ją samą,
  • jeśli wartość low analizowanego wierzchołka będzie równa jego numerowi nadanemu przez DFS, to oznacza, że krawędź z tego wierzchołka do jego ojca jest mostem.

Zadanie.

Napisz program, który znajdzie wszystkie mosty w spójnym grafie niewagowym i nieskierowanym

Wejście

W pierwszym wierszu dwie liczby n oraz m określające liczbę wierzchołków, oraz liczbę dwukierunkowych połączeń między nimi (2 ≤ n ≤ 500000; 1 ≤ m ≤ 1000000). W każdym z kolejnych m wierszy znajdują się dwie liczby naturalne a i b (1 ≤ a ≠ b ≤ n) oznaczające, że wierzchołki a i b są połączone krawędzią.

Wyjście

Na wyjściu należy wypisać wszystkie pary krawędzi a, b pomiędzy którymi jest most.

//wyszukiwanie mostów w grafie
//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;

struct G{
	vector <int> pol; //połączenia
	int low, ojciec, //wartość low, ojciec tego wierzchołka
		nr;			//numer wierzchołka nadany przez DFS_NADAJ_NR
	bool odw;		//czy odwiedzony
}*w;

int nr = 1; //do numerowania wierzchołków
vector <pair<int, int> > mosty;	

void DFS_NADAJ_NR(int n, int ojciec)
{
	w[n].odw = 1;
	w[n].nr = w[n].low = nr++;
	w[n].ojciec = ojciec;
	
	for(int i=0;i<w[n].pol.size();i++)
		if(!w[w[n].pol[i]].odw)
			DFS_NADAJ_NR(w[n].pol[i], n);
}

void DFS_WYSZUKAJ_MOSTY(int n)
{
	w[n].odw = 1;
	for(int i=0;i<w[n].pol.size();i++)
		if(!w[w[n].pol[i]].odw)
			DFS_WYSZUKAJ_MOSTY(w[n].pol[i]);
				
	//analizowanie przetworzonych wierzchołków
	for(int i=0;i<w[n].pol.size();i++)
		if(w[n].pol[i] != w[n].ojciec)
			w[n].low = min(w[n].low, w[w[n].pol[i]].low);
			
	//sprawdzenie, czy krawędź ojciec - > n jest mostem
	if(w[n].low == w[n].nr && w[n].ojciec > 0)
		mosty.push_back({w[n].ojciec, n});	
}

int main()
{
	int V, E, a, b;
	cout<<"Podaj liczbę wierzchołków: ";
	cin>>V;
	cout<<"Podaj liczbę krawędzi: ";
	cin>>E;
	w = new G[V+1];
	for(int i=0;i<E;i++)
	{
		cout<<i+1<<": ";
		cin>>a>>b;
		w[a].pol.push_back(b);
		w[b].pol.push_back(a);
	}
	
	for(int i=0; i<=V; i++)
		w[i].odw = 0;
	
	DFS_NADAJ_NR(1, 0);
	
	for(int i=0; i<=V; i++)
		w[i].odw = 0;
		
	DFS_WYSZUKAJ_MOSTY(1);
	
	cout<<"Znalezione mosty:\n";
	for(int i=0;i<mosty.size();i++)
		cout<<mosty[i].first<<' '<<mosty[i].second<<endl;
	
	return 0;
}