Pagini recente » Cod sursa (job #868145) | Cod sursa (job #1229487) | Cod sursa (job #941556) | Cod sursa (job #880232) | Cod sursa (job #200063)
Cod sursa(job #200063)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/********************************************
Type: Graph, defines a graph type:
- lista de adiacentza
- n numarul de noduri
1 la n
/********************************************/
typedef struct {
vector<vector<int> > E; //muchiile
vector<int> degree; //gradele
int n; //numarul de noduri
void init(int _n) //initializeaza un graph gol cu N noduri
{
E.resize(_n + 3);
degree.resize(_n + 3);
n = _n;
}
void addEdge(int a, int b) //pune edge de la a la b
{
++degree[a];
E[a].push_back(b);
}
//DFS algorithm - only if initiated
vector<int> processed; //contine -1, sau componenta din care face parte
int componente; //contine numarul de componnete
void initDFS() {processed.resize(n + 3, -1); componente = 0;}
void eraseDFS() {processed.clear();} //erase de DFS, to clear memory
void runDFS(int nod, int color)
{
if (processed[nod] != -1) return;
processed[nod] = color;
for (int i = 0; i < degree[nod]; ++i) runDFS(E[nod][i], color);
}
void dfs() {
initDFS(); //initiaza
for (int i = 1; i <= n; ++i) if (processed[i] == -1)
{
++componente;
runDFS(i, componente);
}
}
} graph;
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int N, M; //N numarul de noduri, M - numarul de muchii
scanf("%d %d", &N, &M); //citeste N si M
graph G; //graful nostru
G.init(N); //initiaza graf gol cu N noduri
int i, j, k; //variabile
//let's read the muchii
while (M--) {
int a, b;
scanf("%d %d", &a, &b);
G.addEdge(a, b); //add a -> b
G.addEdge(b, a); //add b -> a
}
G.dfs(); //run DFS algorithm
printf("%d\n", G.componente);
G.eraseDFS(); //erase DFS data
return 0;
}