Cod sursa(job #1451108)

Utilizator RuxyRezidentTMRuxandra P RuxyRezidentTM Data 16 iunie 2015 00:42:46
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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;
}