Cod sursa(job #1450903)

Utilizator RuxyRezidentTMRuxandra P RuxyRezidentTM Data 15 iunie 2015 03:30:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <vector>
using namespace std;

int m, n, nodes = 0;
vector<int> visited;
vector< vector<int> > graph;
FILE *in = fopen ("dfs.in" , "r");
FILE *out = fopen ("dfs.out" , "w");


void dfs(int x) {
    visited[x] = 1;
    nodes++;
    if(nodes == n)
        return;
    vector<int> list = graph.at(x);
    for(vector<int>::const_iterator it = list.begin(); it != list.end(); it++) {
           if(visited[*it] == 0)
            dfs(*it);
    }
}

int components() {

    int comp = 0;
    for(int i = 1; i <= n; i++) {
          if(visited[i] == 0) {
               comp++;
               dfs(i);
           }
    }
    return comp;
}

int main()
{


    fscanf(in, "%d %d", &n, &m);
    graph = vector< vector<int> >(n + 1, vector<int>());
    visited = vector<int> (n+1, 0);
    int x, y;
    for(int i = 1; i <= m; i++) {
        fscanf(in, "%d %d", &x, &y);
        graph.at(x).push_back(y);
        if(x != y)
            graph.at(y).push_back(x);
    }
//    int index = 0;
//    for(vector< vector<int> >::const_iterator it = graph.begin(); it != graph.end(); it++, index++) {
//        for(vector<int>::const_iterator jt = it->begin(); jt != it->end(); jt++) {
//           fprintf(out, "%d %d\n", index , *jt);
//        }
//
//    }

    int comp = components();
    fprintf(out, "%d\n", comp);
    fclose(in);
    fclose(out);
    return 0;
}