Cod sursa(job #3262701)

Utilizator EnnBruhEne Andrei EnnBruh Data 11 decembrie 2024 12:51:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;


#define inFile "dfs.in"
#define outFIle "dfs.out"

FILE *in  = fopen(inFile, "r");
FILE *out = fopen(outFIle, "w");

#define maxSize 100002
#define inf INT_MAX

vector <int> adj[maxSize];
bitset <maxSize> visited;
void depthSearch(int curNode) {
        for (auto curNeibor : adj[curNode]) {
                if (visited[curNeibor]) continue ;
                visited[curNeibor] = true;
                depthSearch( curNeibor );
        }
}

int main( ) {
        int numNodes, numEdges; fscanf(in, "%d %d", &numNodes, &numEdges);
        int nodeA, nodeB;
        for (int i = 0; i < numEdges; ++i) {
                fscanf(in, "%d %d", &nodeA, &nodeB);
                adj[nodeA].push_back( nodeB );
                adj[nodeB].push_back( nodeA );
        }

        int numComponents = 0;
        for (int curNode = 1; curNode <= numNodes; ++curNode)
                if (!visited[curNode]) {
                        ++numComponents;
                        depthSearch( curNode );
                }

        fprintf(out, "%d\n", numComponents);
        return 0;
}