Pagini recente » Cod sursa (job #3206727) | Cod sursa (job #204322) | Cod sursa (job #907457) | Cod sursa (job #1905721) | Cod sursa (job #1087248)
#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[i].a--;
v[i].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';
}