Pagini recente » Cod sursa (job #1969818) | Borderou de evaluare (job #1765718) | Cod sursa (job #760367) | Cod sursa (job #2527245) | Cod sursa (job #1354100)
#include <fstream>
using namespace std;
ofstream g("dfs.out");
int N, M, nr;
bool vizitat[100001];
struct nod{int info; nod *urm;} *li[100001];
nod *p;
void push(nod *&li, int informatie)
{
p=new nod();
p->info=informatie;
p->urm=li;
li=p;
}
void pop(nod *&li)
{
p=li;
li=li->urm;
delete(p);
}
int top(nod *li)
{
return li->info;
}
bool gol(nod *li)
{
if(!li || li->info==0) return true;
else return false;
}
void DFS(int A)
{
nod *p;
vizitat[A]=true;
while(!gol(li[A]))
{
if(!vizitat[top(li[A])])
DFS(top(li[A]));
pop(li[A]);
}
}
int main()
{
int i, x, y;
FILE *f; f=fopen("dfs.in", "r");
fscanf(f, "%d%d", &N, &M);
for(i=1;i<=M;i++)
{
fscanf(f, "%d%d", &x, &y);
push(li[x], y);
push(li[y], x);
}
/*
for(i=1;i<=N;i++)
{
while(!gol(li[i]))
{
g<<top(li[i])<<" ";
pop(li[i]);
}
g<<'\n';
}
*/
for(i=1;i<=N;i++)
if(!vizitat[i]) nr++, DFS(i);
g<<nr;
return 0;
}