Cod sursa(job #1094209)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 28 ianuarie 2014 23:58:42
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
#define dmax 100000
int use[dmax];
int n, m;
vector <int> v[dmax];

void read()
{
    int a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {fin>>a>>b;
    v[a].push_back(b);
    v[b].push_back(a);


    }
}


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

int main()
{
    read();
    int k=0;
    for(int i=1;i<=n;i++)
        if(!use[i])
        {
            k++;
            dfs(i);

        }
fout<<k<<'\n';
    return 0;
}