Cod sursa(job #2139682)

Utilizator inquisitorAnders inquisitor Data 22 februarie 2018 18:28:19
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

#define BUFFSIZE 1<<17

FILE *F=fopen("dfs.in", "r"), *G=fopen("dfs.out", "w");

int n, m, x, y, grd[100005], L[100005], g[200005], K;
bitset<100005> v;
vector<pair<int, int> > a;
char buf[BUFFSIZE];
int pos=BUFFSIZE;

inline char nextch(){
    if(pos==BUFFSIZE){
        fread(buf, BUFFSIZE, 1, F);
        pos=0;
    }
    return buf[pos++];
}

inline int read(){
    char ch = nextch();
    while(!isdigit(ch)) ch=nextch();
    int nr= ch-'0';
    while(isdigit(ch=nextch())) nr = nr*10+ch-'0';
    return nr;
}

inline void dfs(int nod){
    v[nod]=1;
    int x = grd[nod-1];
    int y = grd[nod];
    for(int i = x; i < y; ++ i){
        if(!v[g[i]]){
            dfs(g[i]);
        }
    }
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; ++ i){
        x=read(); y = read();

        a.push_back({x, y});
    }

    for(int i = 1; i <= n; ++ i){
        if(!v[i]){
            dfs(i);
            K++;
        }
    }
    fprintf(G, "%d",K);
    return 0;
}