Cod sursa(job #2242225)

Utilizator mihaicivMihai Vlad mihaiciv Data 18 septembrie 2018 09:24:19
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#define nmax 100100
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m, Size[nmax], vis[nmax];
int **a = new int *[nmax];
void Read() {
    f >> n >> m;
    for (int i = 1;i <= n;i ++) {
        a[i] = new int[nmax];
        Size[i] = 0;
    }
    int x, y;
    for (int i = 1;i <= m;i ++) {
        f >> x >> y;
        a[x][Size[x]] = y;
        Size[x] ++;
        a[y][Size[y]] = x;
        Size[y] ++;
    }
}
void DFS(int x) {
    vis[x] = 1;
    for (int i = 0;i < Size[x]; i ++) {
        int p = a[x][i];
        if (vis[p] == 0) {
            DFS(p);
        }
    }
}
void Solve() {
    int Ans = 0;
    for (int i = 1;i <= n;i ++) {
        if (vis[i] == 0 ) {
            Ans ++;
            DFS(i);
        }
    }
     g << Ans;
}
int main() {
    Read();
    Solve();
    return 0;
}