Spójność grafu

Mam takie zadanie:
http://solve.edu.pl/contests/download_desc/2011

Mam taki kod ale coś nie działa do końca poprawnie :-( bo przechodzi jeden test :-(
Może ktoś widzi błąd?

#include <iostream>
#include <algorithm>
using namespace std;
int tab[1000001];
bool czy[1000001];
int FIND(int u)
{
    if (tab[u] != u) {
        tab[u] = FIND(tab[u]);
    }
    return tab[u];
}

void UNION(int u, int v)
{
    tab[FIND(u)] = FIND(v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, p;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int w = 1; w <= 1000000; w++) {
            tab[w] = w;
        }
        cin >> q >> p;
        for (int j = 1; j <= p; j++) {
            int a, b;
            cin >> a >> b;
            UNION(a, b);
        }
        int rozne = 1;
        for (int b = 1; b < q; b++) {
            if (tab[b] != tab[b + 1]) {
                rozne++;
            }
        }

        //    cout<<rozne<<endl;
        if (rozne == 1) {
            czy[i] = true;
        }
        else
            czy[i] = false;
    }

    for (int i = 0; i < n; i++) {
        if (czy[i] == true) {
            cout << "TAK"
                 << "\n";
        }
        else
            cout << "NIE"
                 << "\n";
    }
    return 0;
}

Pokaż zbiory testowe na których Ci to przechodzi.
Czy są wśród nich wszystkie przypadki testowe, które możesz sobie wyobrazić?

Czemu sobie nie Zaimplementujesz grafu (jako nowy ADT)? I nie Zapuścisz na nim jakiegoś przeszukiwania? Najprościej można tak:

using graph = std::map<int, std::vector<int>>;

Namieszałeś strasznie. Po co tu robić find & union. Zrób graf. Powyżej masz przykładowy kod. Ja robiłem w C++ zawsze w taki sposób:

vector<int> graph[MAX];

Gdzie MAX to stała posiadająca w której jest maksymalna ilość wierzchołków w zadaniu.

Dalej robisz algorytm DFS. Jeżeli pętla zewnętrzna weszła do środka drugi raz to graf nie jest spójny, w przeciwnym przypadku jest. Możesz to zrobić też pewnie find & union, ale nie musisz.

A w tym kodzie co mam można coś zmienić aby było lepiej ?

Nie wiem (przynajmniej ja), nie widze tu grafu nie widzę DFS, BFS czy jakiegokolwiek algorytmu przeszukiwania. Nie mam punktu zaczepienia.

Cześć,

mam taki kod ale dalej coś nie działa poprawnie.
Dla danych wyjściowych pokazuje mi błędną odpowiedź :-(
Powinno być:

Wejście:
2
3 3
1 2
2 3
1 3

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

Wyjście:
TAK
NIE

A pokazuje mi:
NIE
NIE
:-(

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

bool visited[10000];
vector < int >V[10000];

int
main ()
{
// liczba testów
  int t;
  cin >> t;
  while (t--)
    {
      int n, m, i, v1, v2;
      bool spojny;
      stack < int >S;

      cin >> n >> m;

      for (i = 0; i < m; i++)
	{
	  cin >> v1 >> v2;
	  V[v1].push_back (v2);
	  V[v2].push_back (v1);
	}

      for (i = 0; i < n; i++)
	{

	}

      cout << "\n";

// Za pomoca DFS przechodzimy graf od wierzcholka startowego

      S.push (0);
      while (!S.empty ())
	{
	  v1 = S.top ();
	  S.pop ();
	  if (!visited[v1])
	    {
	      visited[v1] = true;
	      for (int i = 0; i < V[v1].size (); i++)
		if (!visited[V[v1][i]])
		  {
		    S.push (V[v1][i]);
		  }
	    }
	}
// Sprawdzamy, czy DFS odwiedzil wszystkie wierzcholki
      spojny = true;
      for (i = 0; i < n; i++)
	if (!visited[i])
	  {
	    spojny = false;
	    break;
	  }

      cout << endl;
      if (spojny)
	cout << "TAK";
      else
	cout << "NIE";
    }
}

Może ktoś widzi błąd?

porównaj sobie czytelność twojego i mojego kodu:
https://wandbox.org/permlink/t3Jiep4yiRqroNBk
Na razie nie widzę błędu u ciebie.

• brak czyszczenia visited dla kolejnego testu, ale to nie tłumaczy błędnej odpowiedzi dla pierwszego testu.

---

dobra już widzę na czym u ciebie polega błąd. Poplątałeś zakresy indeksów. Raz używasz indeksów od `0` do `n-1`, a raz indeksów od `1` do `n`. Efekt jest taki, że zero nie jest z czymkolwiek połączone. https://wandbox.org/permlink/06frDvDjlCka8xcA

Naucz się korzystać z debugger-a, wtedy wykryłbyś ten błąd dosłownie w minutkę.