Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- int N,M;
- bool viz[1001];
- int a[1001][1001];
- /**
- Se da un graf neoirentat.
- Sa se spuna cate componente conexe are.
- Se vor citi din fisier:
- N = numarul de noduri(varfuri) din graf,
- numerotate de la 1 la n
- M = numarul de muchii din graf
- pe urmatoarele M linii se vor citi cate doua numere naturale,
- x y, cu semnificatia "exista muchie de la nodul x la nodul y"
- */
- ///depth first search
- ///parcurgere in adancime
- void DFS(int x)
- {
- int i,y,nr_vecini;
- viz[x] = true;
- nr_vecini = a[x][0];
- for(i=1;i<=nr_vecini;i++)
- {
- y = a[x][i];
- ///y este un vecin al lui x
- if(viz[y]==false)//daca y nu a fost inca vizitat
- DFS(y);
- }
- }
- int main()
- {
- int i,x,y;
- ifstream fin("graf.in");
- fin>>N>>M;
- ///In a[i][0] vom retine numarul de vecini ai nodului i
- for(i=1;i<=N;i++)
- {
- a[i][0] = 0;
- viz[i] = false;
- }
- ///acum citim toate muchiile
- for(i=1;i<=M;i++)
- {
- fin>>x>>y;
- ///daca am fi folosit o matrice de adiacenta, am fi scris a[x][y] = 1; a[y][x] = 1;
- a[x][0]++;
- a[x][a[x][0]] = y;
- a[y][0]++;
- a[y][a[y][0]] = x;
- }
- fin.close();
- ///SOLUTIE:
- int nr_componente_conexe=0;
- for(i=1;i<=N;i++)
- if(!viz[i])
- {
- DFS(i);
- nr_componente_conexe++;
- }
- cout<<nr_componente_conexe<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement