Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- /**
- Se da un graf neorientat. Calculati distantele de la 1 la toate
- celelalte noduri, folosind DFS(chiar daca in mod normal se face cu BFS).
- */
- int n,m;
- vector<int>L[100003];
- int d[100003];
- const int INF = 2000000000;
- void citire()
- {
- int i,x,y;
- ifstream fin("date.in");
- fin>>n>>m;
- for(i=1;i<=m;i++)
- {
- fin>>x>>y;
- L[x].push_back(y);
- L[y].push_back(x);
- }
- fin.close();
- }
- void dfs(int x)
- {
- int i,y;
- for(i=0;i<L[x].size();i++)
- {
- y=L[x][i];
- if( d[y] > d[x] + 1 )
- {
- d[y] = d[x] + 1;
- dfs(y);
- }
- }
- }
- void afisare()
- {
- int i;
- ofstream fout("date.out");
- for(i=1;i<=n;++i)
- fout<<d[i]<<" ";
- fout.close();
- }
- int main()
- {
- citire();
- int i;
- for(i=1;i<=n;++i)
- d[i] = INF;
- d[1]=0;
- dfs(1);
- afisare();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement