Cod sursa(job #1076404)

Utilizator DDeidaraSzasz Tamas Csaba DDeidara Data 10 ianuarie 2014 09:51:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>

using namespace std;

int n,m;
int res = 0;
vector <int> list[100001];
bool w[100001] = {false};

void dfs(int nod)
{
    w[nod] = true;
    for (vector<int>::iterator it = list[nod].begin();
         it!=list[nod].end();++it)
             if (!w[*it]) dfs(*it);
}

int main()
{
    FILE*f;
    f = fopen("dfs.in","r");
    fscanf(f,"%d %d",&n,&m);

    int a,b;
    for (int i = 0; i != m; ++i)
    {
        fscanf(f,"%d %d",&a,&b);
        list[a].push_back(b);
        list[b].push_back(a);

    }
    fclose(f);

    for (int i = 1; i <= n; ++i)
     if (!w[i])
     {
         ++res;
         dfs(i);
     }

    f = fopen("dfs.out","w");
    fprintf(f,"%d",res);
    fclose(f);

    return 0;
}