Cod sursa(job #1087249)

Utilizator IeewIordache Bogdan Ieew Data 19 ianuarie 2014 03:52:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <stdlib.h>

using namespace std;

#define DEBUG false
#define MAXN 100000
#define MAXM 200000

struct node {
    int start;
    int length;
}a[MAXN];

struct edge{
    int a,b;
}v[MAXM];

#if DEBUG
#include <iostream>
#define INFILE "/Users/biordach/Documents/Xcode Projects/training/training/dfs.in"
#define __OUT cout
#else
#define INFILE "dfs.in"
#define OUTFILE "dfs.out"
ofstream __OUT(OUTFILE);
#endif

int n, m, sol;
bool viz[MAXN];

void readInput();
void solve();
void printOutput();

int main(int argc, const char * argv[])
{
    readInput();
    solve();
    printOutput();

#if DEBUG == false
    __OUT.close();
#endif
    
    return 0;
}

void readInput(){
    ifstream in(INFILE);
    in>>n>>m;
    int k = 0;
    for(int i=0;i<m;i++){
        in>>v[k].a >> v[k].b;
        v[k].a--;
        v[k].b -- ;
        k++;
        v[k].a = v[k-1].b;
        v[k].b = v[k-1].a;
        k++;
    }
    in.close();
}

int sortf(const void *a, const void *b){
    edge *aa = (edge*)a, *bb = (edge*)b;
    return aa->a - bb->a;
}

void dfs(int x){
    viz[x] = 1;
    for(int i = a[x].start; i < a[x].start + a[x].length; i++){
        if(!viz[v[i].b]){
            dfs(v[i].b);
        }
    }
    
}

void solve(){
    qsort(v, 2 * m, sizeof(edge), sortf);

    int current = v[0].a;
    int len = 1;
    a[current].start = 0;

    for(int i=1;i<2 * m;i++){
        if(v[i].a == current){
            len ++;
        } else {
            a[current].length = len;
            current = v[i].a;
            a[current].start = i;
            len = 1;
        }
    }
    a[current].length = len;

    for(int i=0;i<n;i++){
        if(!viz[i]) {
            dfs(i);
            sol ++;
        }
    }
    
}

void printOutput(){
    __OUT<<sol<<'\n';
}