Cod sursa(job #2028954)

Utilizator bcrisBianca Cristina bcris Data 28 septembrie 2017 21:13:49
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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);
    }

 
   	for (int i = 1; i <= n; i++) {
    	if (visited[i] == 0) {
    		dfs(i);
    		no_components++;
    	}	
    }
    
    printf("%d\n", no_components);	

    return 0;
}