Cod sursa(job #545913)

Utilizator KosmynC64Munteanu Cosmin KosmynC64 Data 4 martie 2011 09:22:50
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
struct nod{
int visited;
vector<nod*> next;};
int dfs(vector<nod*> graf,nod*start){
    start->visited=0;
    for(int i=0;i<start->next.size();i++)
    if(start->next[i]->visited==0)
    dfs(graf,start->next[i]);
return 0;}
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;
    dfs(graf,graf[i]);}

    ofstream g("dfs.out");
    g<<conex;
    g.close();
return 0;}