Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// DFS
- /// ========
- /// https://www.infoarena.ro/job_detail/2535791?action=view-source
- #include <iostream>
- #include <fstream>
- #include <vector>
- #define MAX 100001
- using namespace std;
- ifstream ci ("dfs.in");
- ofstream co ("dfs.out");
- vector<int>NOD[MAX];
- bool viz[MAX];
- int n,m;
- int x,y;
- void DFS (int x)
- {
- viz[x]=true;
- for (unsigned int i=0;i<NOD[x].size();++i)
- {
- if (viz[NOD[x][i]]==false)
- {
- DFS(NOD[x][i]);
- }
- }
- }
- int main ()
- {
- ci>>n>>m;
- while (m)
- {
- m--;
- ci>>x>>y;
- NOD[x].push_back(y);
- NOD[y].push_back(x);
- }
- int temp=0;
- for (int i=1;i<=n;++i)
- {
- // temp++;
- if (viz[i]==false)
- {
- temp++;
- DFS(i);
- }
- }
- co<<temp;
- return 0;
- }
- /// BFS
- /// ================
- #include <bits/stdc++.h>
- /// https://www.infoarena.ro/job_detail/2537114?action=view-source
- using namespace std;
- const int MAX = 100001;
- vector <int> nod[MAX];
- deque <int> coada;
- int viz[MAX], n, m, s, lung[MAX];
- ifstream in ("bfs.in");
- ofstream out ("bfs.out");
- int BFS()
- {
- int x;
- coada.push_back(s);
- viz[s] = 1;
- lung[s] = 0;
- while(!coada.empty())
- {
- x = coada.front();
- coada.pop_front();
- for(int i = 0; i < nod[x].size(); i++)
- {
- if(!viz[nod[x][i]])
- {
- coada.push_back(nod[x][i]);
- lung[nod[x][i]] = lung[x] + 1;
- viz[nod[x][i]] = 1;
- }
- }
- }
- }
- int main()
- {
- int x, y;
- in >> n >> m >> s;
- while(m)
- {
- m--;
- in >> x >> y;
- nod[x].push_back(y);
- }
- for(int i = 1; i <= n; i++)
- {
- lung[i] = -1;
- }
- BFS();
- for(int i = 1; i <= n; i++)
- {
- out << lung[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement