Pagini recente » Cod sursa (job #5532) | Cod sursa (job #1346318) | Cod sursa (job #257876) | Cod sursa (job #2448124) | Cod sursa (job #1504845)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
/*int v[1001][1001], vf, nr=0, n;
void df(int k)
{
//cout<<"Defeu!\n";
int i=1;
viz[k]=1;
for(i=1;i<=n;i++)
{
if(!viz[i] && v[k][i] )
df(i);
}
}
int main()
{
ifstream g ("dfs.in");
ofstream h ("dfs.out");
int m, x, y, i;
g>>n>>m;
for(i=0;i<m;i++)
{
//cout<<"Citire OK!\n";
g>>x>>y;
v[x][y]=1;
v[y][x]=1;
}
//df-probabil recursiv
for(i=1;i<=n;i++)
{
//cout<<"For OK!\n";
if(!viz[i])
{
nr++;
df(i);
}
}
h<<nr;
}*/
int viz[100001];
class nod
{
public:
int nr=0;
vector <int> v;
} a[100001];
void df(int k)
{
int i=1;
viz[k]=1;
for(i=0;i<a[k].nr;i++)
{
if(!viz[a[k].v[i]] )
df(a[k].v[i]);
}
}
int main ()
{
ifstream g ("dfs.in");
ofstream h ("dfs.out");
int m, n, x, y, i, j=0;
g>>n>>m;
for(i=0;i<m;i++)
{
//cout<<"Citire OK!\n";
g>>x>>y;
a[x].v.push_back(y);
a[x].nr++;
a[y].v.push_back(x);
a[y].nr++;
}
for(i=1;i<=n;i++)
{
//cout<<"For OK!\n";
if(!viz[i])
{
j++;
df(i);
}
}
//for(i=1;i<=n;i++)
// cout<<viz[i]<<" ";
//cout<<sizeof(a)<<" "<<sizeof(viz);
h<<j;
g.close();
h.close();
return 0;
}