Cod sursa(job #2629186)

Utilizator doyouhavethetimeStanculescu Gabriel doyouhavethetime Data 19 iunie 2020 13:54:08
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

int read () {
    int ch;
    while (!isdigit(ch=getchar()));

    int ans=0;
    do
        ans = (ans<<3) + (ans<<1) + ch - '0';
    while (isdigit(ch=getchar()));

    return ans;
}

void print (int a) {
    if (a) {
        print(a/10);
        putchar(a%10 + '0');
    }
}

struct nod {
    int inf;
    struct nod *urm;
} **G;

void add (struct nod **p, int x) {
    struct nod *e = (struct nod*) malloc(sizeof (struct nod));
    e->inf=x;
    e->urm=*p;
    *p=e;
}

unsigned long long *bits;
void set (int i) {
    bits[i>>6] |= (1ull << (i & 63));
}

int seen (int i) {
    return (bits[i>>6] >> (i & 63)) & 1;
}

void dfs (int x) {
    set(x);
    for (struct nod *p=G[x]; p; p=p->urm)
        if (!seen(p->inf))
            dfs(p->inf);
}

int main (void) {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    int n, m;
    n=read(), m=read();

    bits = (unsigned long long*) calloc((n>>6) + 1, sizeof (unsigned long long));
    G = (struct nod**) calloc(n+1, sizeof (struct nod*));

    int i, j, ct=0;
    for (; m; m--) {
        i=read();
        j=read();
        add(G+i, j);
    }

    for (i=1; i<=n; ++i)
        if (!seen(i)) {
            ++ct;
            dfs(i);
        }

    print(ct);
    return 0;
}