Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //ofstream fout("prob1.out");
- vector <int> v[100010];
- int a[1000];
- int n,m,x,y,k,w;queue <int> q;bool check=false;
- bool viz[100010];
- void dfs(int nod){
- viz[nod]=1;cout<<nod<<' ';
- for(int i=0;i<v[nod].size();i++)
- if(!viz[v[nod][i]])viz[v[nod][i]]=1,dfs(v[nod][i]);
- }
- void bfs(int s){
- q.push(s);
- viz[s]=1;
- while(!q.empty()){
- int s=q.front();cout<<s<<' ';
- q.pop();
- for(int i=0;i<v[s].size();i++){
- if(!viz[v[s][i]])q.push(v[s][i]),viz[v[s][i]]=1;
- }
- }
- }
- void dfs1(int nod){
- viz[nod]=1;
- for(int i=0;i<v[nod].size();i++){
- if(v[nod][i]==w){
- cout<<"Este ciclu"<<endl;
- check=true;return;
- }else
- if(!viz[v[nod][i]])viz[v[nod][i]]=1,dfs1(v[nod][i]);}
- }
- int main(){
- ifstream cin("prob1.in");
- //ofstream cout("prob1.out");
- cin>>n>>m;
- for(int i=1;i<=m;i++){
- cin>>x>>y;
- v[x].push_back(y);
- v[y].push_back(x);
- }
- cout<<endl;
- for(int i=1;i<=n;i++){
- cout<<i<<':';
- for(int j=v[i].size()-1;j>=0;j--)
- cout<<v[i][j]<<' ';
- cout<<endl;
- }cout<<endl;cout<<"Dfs:";
- for(int i=1;i<=n;i++)
- if(!viz[i]){
- dfs(i);
- k++;
- }cout<<endl;
- for(int i=1;i<=n;i++)viz[i]=0;
- if(k!=1)cout<<"Componente conexe :"<<k<<endl;else cout<<"Graful e conex"<<endl;
- cout<<"Bfs:";
- for(int i=1;i<=n;i++)
- if(!viz[i]){
- bfs(i);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement