Pagini recente » Cod sursa (job #1354162) | Cod sursa (job #1667338) | Cod sursa (job #2305704) | Cod sursa (job #997666) | Cod sursa (job #2510435)
#include <fstream>
using namespace std;
int t[100001],niv[100001];
int f(int x)
{
int y=x,i;
while (t[y])
y=t[y];
while(t[x])
{
i=t[x];
t[x]=y;
x=i;
}
return y;
}
void u(int x, int y)
{
int r1=f(x);
int r2=f(y);
if (r1!=r2)
{
if (niv[r1]==niv[r2])
{
t[r1]=r2;
niv[r2]++;
}
else if (niv[r1]>niv[r2])
t[r2]=r1;
else
t[r1]=r2;
}
}
int main()
{
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n,m,p,x,y,c=0;
fin>>n>>m;
for (int i=1;i<=m;i++)
{
fin>>x>>y;
u(x,y);
}
for (int i=1;i<=n;i++)
if(!t[i])
c++;
fout<<c;
return 0;
}