Cod sursa(job #2139526)

Utilizator inquisitorAnders inquisitor Data 22 februarie 2018 16:52:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

int vertices, edges, u, v, conexParts;

vector<int> adj[100001];

bool visited[100001];

void DFS(int start)
{
    stack<int> s;

    s.push(start);

    while(!s.empty())
    {
        int current = s.top(); s.pop();

        if(visited[current] == false)
        {
            for(int child : adj[current])
            {
                s.push(child);
            }

            visited[current] = true;
        }
    }
}

__attribute__((always_inline)) void read(int &num)
{
    static char inBuffer[0x30D40];

    static unsigned int p = 0x30D3F; num = 0x0;

    while(inBuffer[p] < 0x30 | inBuffer[p] > 0x39)
    {
        ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
    }

    while(inBuffer[p] > 0x2F & inBuffer[p] < 0x3A)
    {
        num = num * 0xA + inBuffer[p] - 0x30;

        ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
    }
}

int main(){

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

    read(vertices); read(edges);

    for(int i = 1; i <= edges; i++)
    {
        read(u), read(v);

        adj[u].push_back(v);

        adj[v].push_back(u);
    }

    for(int i = 1; i <= vertices; i++)
    {
        if(visited[i] == false)
        {
            DFS(i);

            conexParts++;
        }
    }

    printf("%d", conexParts);

    return 0;
}