Pagini recente » Cod sursa (job #1186530) | Cod sursa (job #742359) | Cod sursa (job #2309977) | Cod sursa (job #1554270) | Cod sursa (job #475803)
Cod sursa(job #475803)
#include <fstream>
using namespace std;
struct arc{int x,y;} a[1<<19];
int s[1<<17],n,m;
bool use[1<<17];
ifstream in("dfs.in");
ofstream out("dfs.out");
void set(int x)
{
use[x]=true;
for (int i=s[x];i<s[x+1];i++)
if (!use[a[i].y])
set(a[i].y);
}
bool cmp(arc a,arc b)
{
return a.x<b.x;
}
int main()
{
int i,j,nr=0;
in>>n>>m;
for (i=1;i<=m;i++)
{
in>>a[i].x>>a[i].y;
a[i+m].x=a[i].y;
a[i+m].y=a[i].x;
}
m<<=1;
sort(a+1,a+m+1,cmp);
for (i=j=1;i<=n;s[i]=j,i++)
for (;j<=m && a[j].x<i;j++);
s[n+1]=m+1;
for (i=1;i<=n;i++)
if (!use[i])
{
set(i);
nr++;
}
out<<nr<<"\n";
return 0;
}