Cod sursa(job #2227456)

Utilizator inquisitorAnders inquisitor Data 31 iulie 2018 20:00:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>

int vertices, edges, u, v, conexParts, visited[4096];

std :: vector<int> adj[100001];

void DFS(int current)
{
    visited[current >> 5] |= 1 << (current & 0x1F);

    for(int child : adj[current])
    {
        if(!(visited[child >> 5] & 1 << (child & 0x1F)))
        {
            DFS(child);
        }
    }
}

char buffer[20000000]; int p = -1;

__attribute__((always_inline)) int get_int()
{
    int number = 0;

    for(++p; buffer[p] > 47; ++p)
    {
        number = number * 10 + buffer[p] - 48;
    }

    return number;
}

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

    fread(buffer, 1, 20000000, stdin);

    vertices = get_int(), edges = get_int();

    for(int i = edges + 1; --i;)
    {
        u = get_int(), v = get_int();

        adj[u].push_back(v);

        adj[v].push_back(u);
    }

    for(int i = vertices + 1; --i;)
    {
        if(!(visited[i >> 5] & 1 << (i & 0x1F)))
        {
            DFS(i);

            ++conexParts;
        }
    }

    printf("%d", conexParts);

    return 0;
}