Pagini recente » Cod sursa (job #934342) | Cod sursa (job #1934953) | Cod sursa (job #3210444) | Cod sursa (job #1806583) | Cod sursa (job #931105)
Cod sursa(job #931105)
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct nod {
int nd;
nod *next;
};
void read(nod **&a,int &n)
{
int nr;
in >> n >> nr;
// Alocare matrice
a = (nod**)calloc(n+1,sizeof(nod*));
for (int i = 0; i < n+1; ++i)
a[i] = 0;
// Citire graf
for(int i = 0; i < nr; ++i)
{
int x,y;
in >> x >> y;
nod *p = new nod;
p->nd = y;
p->next = a[x];
a[x] = p;
}
}
void print(nod **a,int n)
{
for (int i = 1; i < n+1; ++i)
{
cout<<i<<" | ";
while(a[i])
{
cout<<a[i]->nd<<" ";
a[i] = a[i]->next;
}
cout<<"\n";
}
}
void dfs(int sursa,nod **a,int n,int *&viz)
{
viz[sursa] = 1;
while(a[sursa])
{
int c = a[sursa]->nd;
if( !viz[c] )
dfs(c,a,n,viz);
else
a[sursa] = a[sursa]->next;
}
}
int main()
{
int n;
nod **a;
read(a,n);
//print(a,n);
int *viz = (int*)calloc(n+1,sizeof(int));
int nr = 0;
for(int i = 1; i < n+1; i++)
if(!viz[i])
{
dfs(i,a,n,viz);
nr++;
}
out<<nr;
return 0;
}