Cod sursa(job #2028950)

Utilizator bcrisBianca Cristina bcris Data 28 septembrie 2017 21:10:40
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <vector>
#include <queue>

#define NMAX 100001

int n, m, no_components; 

using namespace std;

vector<int> adj_list[NMAX + 1];
int visited[NMAX + 1];

void dfs(int start) {
	visited[start] = 1;
	for (vector<int>::iterator it = adj_list[start].begin(); it != adj_list[start].end(); ++it) {
		if (visited[*it] == 0) {
			dfs(*it);
		}
	}
}

int next_unmarked() {
	for (int i = 1; i <= n; i++) {
		if (visited[i] == 0)
			return i;
	}

	return -1;
}

int main() {
 
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
     
    scanf("%d %d\n", &n, &m);

    // Create adjiacency list
    for (int i = 0; i < m; i++) {
    	int start_edge, end_edge;
    	scanf("%d %d\n", &start_edge, &end_edge);
    	adj_list[start_edge].push_back(end_edge);
    }

    int next = next_unmarked();
    while(next != -1) {
    	dfs(next);
    	no_components++;
    	next = next_unmarked();
    }
    
    printf("%d\n", no_components);	

    return 0;
}