Pagini recente » Cod sursa (job #628263) | Cod sursa (job #2532907) | Cod sursa (job #673386) | Cod sursa (job #713845) | Cod sursa (job #545909)
Cod sursa(job #545909)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
struct nod{
int visited;
vector<nod*> next;};
int bfs(vector<nod*> graf,nod*start){
queue<nod*> coada;
nod*current;
coada.push(start);
while(coada.size()!=0){
current=coada.front();
coada.pop();
current->visited=1;
for(int i=0;i<current->next.size();i++)
if(current->next[i]->visited==0)
coada.push(current->next[i]);}
return 0;}
int main(){
vector<nod*> graf;
int n,m,d1,d2;
int conex=0;
ifstream f("dfs.in");
f>>n>>m;
for(int i=0;i<n;i++){graf.push_back(new nod);graf[i]->visited=0;}
for(int i=0;i<m;i++){
f>>d1>>d2;
graf[d1-1]->next.push_back(graf[d2-1]);
graf[d2-1]->next.push_back(graf[d1-1]);}
f.close();
for(int i=0;i<n;i++)
if(graf[i]->visited==0){
++conex;
bfs(graf,graf[i]);}
ofstream g("dfs.out");
g<<conex;
g.close();
return 0;}