Pagini recente » Cod sursa (job #2786279) | Cod sursa (job #1950344) | Cod sursa (job #2313679) | Cod sursa (job #1431041) | Cod sursa (job #233008)
Cod sursa(job #233008)
#include<fstream>
using namespace std;
const int N=100005;
bool viz[N];
int *a[N];
int x,y,n,m,d[N];
ofstream out("dfs.out");
void citire ()
{
ifstream in("dfs.in");
in>>n>>m;
while(m--)
{
in>>x>>y;
d[x]++;
d[y]++;
}
in.close ();
}
void aloc ()
{
for(int i=1;i<=n;i++)
{
a[i]=new int[1+d[i]];
a[i][0]=0;
}
}
void completez ()
{
ifstream in2("dfs.in");
in2>>n>>m;
while(m--)
{
in2>>x>>y;
a[x][++a[x][0]]=y;
a[y][++a[y][0]]=x;
}
in2.close();
}
/*void afisare ()
{
for(int i=1;i<=n;i++)
{
out<<i<<": ";
for(int j=1;j<=a[i][0];j++)
out<<a[i][j]<<" ";
out<<"\n";
}
}
*/
void dfs (int x)
{
viz[x]=true;
for(int i=1;i<=a[x][0];i++)
{
y=a[x][i];
if(viz[y]==false)
dfs(y);
}
}
int numar ()
{
int nr=0;
for(int i=1;i<=n;i++)
{
if(viz[i]==false)
{
dfs(i);
nr++;
}
}
return nr;
}
int main ()
{
citire ();
aloc ();
completez ();
//afisare ();
out<<numar();
out.close ();
return 0;
}