Cod sursa(job #200063)

Utilizator romocoderRomo Coder romocoder Data 22 iulie 2008 01:36:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#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;
    }