Cod sursa(job #2467600)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 4 octombrie 2019 17:55:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 100010;

FILE *IN;

int N, M, ans;
bool seen[NMAX];
vector <int> Gph[NMAX];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

void read(){
    int x, y;
    Read(N); Read(M);
    for(int i = 1; i <= M; i++){
        Read(x); Read(y);
        Gph[x].push_back(y);
        Gph[y].push_back(x);
    }
}

bool DFS(int node){
    seen[node] = true;
    for(int i = 0; i < Gph[node].size(); i++){
        if(!seen[Gph[node][i]])
            DFS(Gph[node][i]);
    }
}

int main(){

    IN = fopen("dfs.in", "r");
    freopen("dfs.out", "w", stdout);

    read();

    for(int i = 1; i <= N; i++){
        if(!seen[i]) ans++;
        DFS(i);
    }
    printf("%d", ans);

    return 0;
}