Pagini recente » Cod sursa (job #454101) | Cod sursa (job #1114022) | Cod sursa (job #791541) | Cod sursa (job #949230) | Cod sursa (job #1704361)
// #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;
}