Cod sursa(job #482897)

Utilizator andra23Laura Draghici andra23 Data 5 septembrie 2010 22:08:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
#include<vector>
#define nmax 100005

using namespace std;

vector<int> v[nmax];
int viz[nmax];

void dfs(int nod){
    viz[nod] = 1;
    for (int i = 0; i < v[nod].size(); i++)
        if (viz[v[nod][i]] == 0)
            dfs(v[nod][i]);    
}

int main(){
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int m, n, s;
    f>>n>>m;
    int i, j, p, u, x;
    
    for (i = 1; i <= m; i++){
        f>>p>>u;
        v[p].push_back(u);
        v[u].push_back(p);
    }
    
    int nc = 0;
    for (i = 1; i <= n; i++)
        if (viz[i] == 0){
            nc++;
            dfs(i);
        }   
    
    g<<nc<<'\n';
    
    return 0;
}