Pagini recente » Cod sursa (job #2705770) | Cod sursa (job #1964292) | Cod sursa (job #2654357) | Cod sursa (job #388402) | Cod sursa (job #2125160)
#include <bits/stdc++.h>
using namespace std;
FILE *F=fopen("dfs.in", "r"), *G=fopen("dfs.out", "w");
int n, m, x, y, grd[100005], L[100005], g[200005], K;
bitset<100005> v;
vector<pair<int, int> > a;
void dfs(int nod){
v[nod]=1;
int x = grd[nod-1];
int y = grd[nod];
for(int i = x; i < y; ++ i){
if(!v[g[i]]){
dfs(g[i]);
}
}
}
int main()
{
char ch = fgetc(F);
while(!isdigit(ch)) ch=fgetc(F);
while(isdigit(ch)){
n = n*10+ch-'0';
ch=fgetc(F);
}
while(!isdigit(ch)) ch=fgetc(F);
while(isdigit(ch)){
m = m*10+ch-'0';
ch=fgetc(F);
}
for(int i = 1; i <= m; ++ i){
x=0; y=0;
while(!isdigit(ch)) ch=fgetc(F);
while(isdigit(ch)){
x = x*10+ch-'0';
ch=fgetc(F);
}
while(!isdigit(ch)) ch=fgetc(F);
while(isdigit(ch)){
y = y*10+ch-'0';
ch=fgetc(F);
}
grd[x]++; grd[y]++;
a.push_back({x, y});
}
for(int i = 1; i <= n; ++ i){
grd[i]+=grd[i-1];
L[i]=grd[i-1];
}
for(int i = 1; i <= m; ++ i){
x=a[i-1].first;
y=a[i-1].second;
g[L[x]++]=y;
g[L[y]++]=x;
}
for(int i = 1; i <= n; ++ i){
x = grd[i-1];
y=grd[i];
sort(g+x, g+y);
}
for(int i = 1; i <= n; ++ i){
if(!v[i]){
dfs(i);
K++;
}
}
fprintf(G, "%d",K);
return 0;
}