Cod sursa(job #1726563)

Utilizator Victor24Vasiesiu Victor Victor24 Data 8 iulie 2016 13:13:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

vector <int> v[100005];

int a[100005];

int n, m, cc, x, y, i, j;

void dfs(int node) {
    a[node] = cc;
    for (size_t i = 0; i < v[node].size() ;++i) {
        int x = v[node][i];
        if (a[x] == 0) {
            dfs(x);
        }
    }
}

int main ()

{
    f>>n>>m;


    for (i=1; i<=m; i++)
    {
        f>>x>>y;
        v[ x ].push_back(y);
        v[ y ].push_back(x);
    }

    for (i=1; i<=n; i++)
    {
        if (a[i]==0)
        {
            cc++;
            dfs(i);
        }
       /*     queue<int> q;
            q.push(i);
            while (!q.empty()) {
                x = q.front();
                a[x] = cc;
                q.pop();

                for (j = 0; j < int(v[x].size()); ++j) {
                    y = v[x][j];

                    if (a[y] == 0) {
                        q.push(y);
                    }
                }
            }
        */

    }

    g << cc;

    return 0;
}