Pagini recente » Cod sursa (job #3147095) | Cod sursa (job #995755) | Cod sursa (job #335157) | Cod sursa (job #1639627) | Cod sursa (job #749802)
Cod sursa(job #749802)
// DFS - alocare dinamica
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
const int maxn=100001;
int U[maxn], ans, n, m;
struct point{
int info;
point *urm;
}*G[100001];
void add(int x, int y)
{
point *p;
p=new point;
p->info=y;
p->urm=G[x];
G[x]=p;
}
void citire()
{
int i, j;
f>>n>>m;
for(int k=1; k<=m; ++k)
{
f>>i>>j;
add(i, j);
add(j, i);
}
}
void dfs(int nod)
{
point *p;
U[nod] = 1;
for(p=G[nod]; p!=NULL; p=p->urm)
if(!U[p->info])
dfs(p->info);
}
int main()
{
citire();
for(int i=1; i<=n; ++i)
if(!U[i])
{
++ans;
dfs(i);
}
g<<ans<<"\n";
}