Cod sursa(job #942415)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 22 aprilie 2013 13:41:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int MAXN = 100010;
vector <int> v[MAXN];
int n, m, x, y, nr;
bool used[MAXN];

void dfs(int u)
{
    used[u]=1;
    for(vector<int> :: iterator i=v[u].begin(); i<v[u].end() ; ++i)
        if(used[*i] == 0)
            dfs(*i);
}

int main(){
    int i;
    fin >> n >> m;
    for(i=0; i<m; ++i){
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i=1 ; i<=n ; ++i)
        if(used[i] == 0)
            ++nr , dfs(i);

    fout << nr;

    fin.close();
    fout.close();

    return 0;
}