Sprawdzenie spójności grafu nieskierownego. 
 
 
przykładowe dane:
8 12
0 2 0 4
1 3 1 5
2 3 
3 5 
4 5 4 7 4 6
5 6 
6 2
7 3
 
odp: TAK
 
//SPRAWDZENIE SPOJNOSCI GRAFU
//rozwiazanie dla grafu nieskierowanego
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
 
bool visited[10000];   //deklarujemy tablice odwiedzin -> zaznaczamy wszystkie wierzcholki jako nieodwiedzone
vector <int> V[10000];
 
int main()
{
  int n,m,i,v1,v2;
  bool spojny;
  stack<int>S; 
 
  cin >> n >> m; //wczytujemy n-ilosc wierzolkow m-ilosc krawedzi
  
  // Wczytujemy m krawędzi i umieszczamy w wektorach
  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;     // Odczytujemy krawędź od v1 do v2
    V[v1].push_back(v2); // Do wektora A[v1] dodajemy wierzchołek v2
    V[v2].push_back(v1); // Do wektora A[v2] dodajemy wierzchołek v1
  }
  
// POMOCNICZE wypisujemy liste wierzcholkow - sprawdzamy poprawnosc wczytania danych ->START
for(i = 0; i < n; i++)
{
cout<<"\n"<<i<<" -> ";
    for(int j = 0 ; j < V[i].size() ; j++)
    cout << V[i][j]<<", ";
}
// POMOCNICZE wypisujemy liste wierzcholkow - sprawdzamy poprawnosc wczytania danych ->KONIEC 
 
cout << "\n";
 
// Za pomoca DFS przechodzimy graf od wierzcholka startowego
  S.push(0);    // Na stos wierzchołek startowy: 0
  while(!S.empty())
  {
    v1 = S.top();           // Pobieramy wierzchołek ze szczytu stosu
S.pop();                       // Usuwamy pobrany wierzchołek ze szczytu stosu
    if(!visited[v1])           // Sprawdzamy, czy wierzchołek był odwiedzony
    { // jezeli nie to ˇ
        visited[v1] = true;       // Odwiedzamy go i na stosie umieszczamy sasiadow
        for(int i=0 ; i < V[v1].size() ; i++)   //V[v1].size() - ilosc wierzcholkow na liscie wektora v1
   if(!visited[V[v1][i]]) 
     {
        S.push(V[v1][i]);
     }
    }
  }
 
  //przegladamy zawartosc tablicy visited 1-odwiedzony 0-nieodwiedzony !! POMOCNICZE !!
  for(i = 0; i < n; i++) //!! POMOCNICZE !!
    cout<<visited[i]<<", "; //!! POMOCNICZE !!
  
  // Sprawdzamy, czy DFS odwiedzil wszystkie wierzcholki
  spojny = true;  
  for(i = 0; i < n; i++)
      if(!visited[i])
        {
            spojny = false; break;                
        }
 
  cout << endl;
  // W zalezności od stanu zmiennej spojny wypisujemy odpowiedni komunikat
  if(spojny) cout << "Tak"; else cout << "Nie";
}