Cod sursa(job #1704361)

Utilizator hntrVInatoru Andrei-Ioan hntr Data 18 mai 2016 18:01:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
// #include <iostream>
// #include <vector>
// #include <list>
// #include <fstream> 
// #include <stdio.h>
// #include <string.h>

// #define pb push_back
// using namespace std;

// FILE *f;
// FILE *g;

// void dfs(bool visited[], int v, list<int> *graph) {
// 	// facem nodul curent vizitat
// 	visited[v] = true;

// 	// parcurgem folosind un iterator si apoi, in mod recursiv, verificam daca e ok
// 	for(std::list<int>::iterator it = graph[v].begin(); it != graph[v].end() ; ++it) {
// 		if(!visited[*it]) {
// 			dfs(visited, *it, graph);
// 				// daca rezulta ciclu in mod recursiv
// 		}
		
// 	}
// }

// int main() {
// 	f = fopen("dfs.in", "r+");
// 	g = fopen("dfs.out", "w");
// 	int M, N, x, y, counter = 0, aux;
	
// 	// graful ca un array de liste, nu am nevoie sa fie mai complicat deoarece
// 	// nu avem costuri
// 	std::list<int > *graph;
	
// 	// citim datele de intrare si formam graful
// 	aux = fscanf(f,"%d %d\n", &N, &M);
// 	graph = new list<int>[N + 1];
// 	gra
// 	for(int i = 0 ; i < M ; i++) {
// 		aux = fscanf(f,"%d %d\n", &x, &y);
// 		graph[x].push_back(y);
// 		graph[y].push_back(x);
// 	}
// 	/*
// 	bool *visited = new bool[N + 1];
// 	for(int i = 1 ; i <= N ; i++) {
// 		visited[i] = false;
// 	}

// 	// crestem contorul daca nu e ciclu
// 	// aici parcurgem DFs-ul si are complexitate de O(V+E)
// 	for(int i = 1 ; i <= N ; i++) {
// 		if(visited[i] == false) {
// 			counter++;
// 			//dfs(visited, i, graph);	
			
// 		}
// 	}
// 	*/
// 	fprintf(g, "%d\n", counter);
	

// 	cerr << aux;
// 	return 0;

// }

#include <stdio.h>
 
int n, m, viz[100005], cnt;
 
typedef struct nod
{
    int x;
    nod *a;
} *pNod;
pNod v[100005];
 
void add(pNod &dest, int val)
{
    pNod p;
    p = new nod;
    p -> x = val;
    p -> a = dest;
    dest = p;
}
 
void citire()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i, x, y;
 
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d",&x,&y);
        add(v[x], y);
        add(v[y], x);
    }
}
 
void DFS(int nod)
{
    pNod p;
    viz[nod] = 1;
    for (p = v[nod]; p != NULL; p = p -> a) if (!viz[p -> x]) DFS(p -> x);
}   
 
int main()
{
    citire();
    int i;
    for (i = 1; i <= n; i++) if (!viz[i]) { cnt++; DFS(i);}
    printf("%d\n",cnt);
    return 0;
}