Cod sursa(job #2229980)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 august 2018 17:25:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

#define MaximumEdges 200000
#define MaximumNodes 100000

std::ifstream InFile("dfs.in");
std::ofstream OutFile("dfs.out");


int N, M;
// Assuming the data file won't have duplicate entries we can use a list
std::list <int> Adj[MaximumNodes];

bool Seen[MaximumNodes];
// The answer
int CompCount;

void DFS(int StartingIndex) {
    Seen[StartingIndex] = 1;

    for (auto Index : Adj[StartingIndex])
        if(!Seen[Index])
            DFS(Index);
}

void Citire() {
    InFile >> N >> M;
    for (int i=0, x, y; i<M; i++) {
        InFile >> x >> y;
        // Because I can
        x--, y--;
        Adj[x].push_front(y);
        Adj[y].push_front(x);
    }

    InFile.close();
}

void Rezolvare() {
    for (int i=0; i<N; i++)
        if(!Seen[i]) {
            DFS(i);
            CompCount ++;
        }

    OutFile << CompCount;
}

int main()
{
    Citire();
    Rezolvare();

    InFile.close();
    OutFile.close();

    return 0;
}