Pagini recente » Cod sursa (job #2832563) | Cod sursa (job #1117713) | Cod sursa (job #628934) | Cod sursa (job #2237730) | Cod sursa (job #2357483)
#include <fstream>
using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");
typedef struct
node
{
int date;
node *next;
}*list;
node *head, *temp, *tail, *Lda[100];
int n, m, Mx, M[100], x, y, i, k;
bool viz[100];
void add(int q, node *&head)
{
node *temp=new node;
temp->date=q;
temp->next=head;
head=temp;
}
void dfs(int q)
{
viz[q]=1;
//fo << " " << q;
for(node *head=Lda[q]; head; head=head->next)
if (!viz[head->date]) dfs(head->date);
}
int main()
{
fi >> n >> m;
for(i=1; i<=n; i++) Lda[i]=NULL;
for(i=1; i<=m; i++)
{
fi >> x >> y;
add(y,Lda[x]);
add(x,Lda[y]);
}
//fo << " Nr noduri=" << n << "\n Nr muchii=" << m;
/*fo << "\n\n Listele de adicenta: \n";
for(i=1; i<=n; i++)
{
temp=Lda[i];
fo << " Lda[" << i << "] : ";
while(temp)
{
M[i]++;
fo << temp->date << " -> ";
temp=temp->next;
}
fo << "NULL\n";
if(Mx < M[i]) Mx=M[i];
}*/
/*fo << "\n Grad max=" << Mx;
fo << "\n Nodurile cu grad max :\n";
for(i=1; i<=n; i++)
if (M[i]==Mx) fo << " " << i;*/
//fo << "\n\n Parcurgere in adancime (DFS):\n";
for(i=1; i<=n; i++)
{
if (!viz[i])
{
dfs(i);
k++;
//fo << '\n';
}
}
//fo << '\n';
/*if(k)
{
fo << " Graful nu este conex\n Nr componentelor grafului=" << k;
}
else fo << " Graful este conex";
*/
fo << k;
}