Pagini recente » Cod sursa (job #2248663) | Cod sursa (job #363356) | Cod sursa (job #771118) | Cod sursa (job #2056349) | Cod sursa (job #741329)
Cod sursa(job #741329)
#include <fstream>
const unsigned int SIZE(100001);
struct nod
{
unsigned int value;
struct nod *next;
} *graf [SIZE];
bool mark [SIZE];
inline void push (struct nod *&first, unsigned int value)
{
struct nod *new_nod(new struct nod);
new_nod->value = value;
new_nod->next = first;
first = new_nod;
}
void DepthFirstSearch (unsigned int value)
{
mark[value] = true;
struct nod *i(graf[value]);
while (i)
{
if (!mark[i->value])
DepthFirstSearch(i->value);
i = i->next;
}
}
int main (void)
{
unsigned int n,m;
std::ifstream input("dfs.in");
input >> n >> m;
unsigned int x,y;
do
{
input >> x >> y;
push(graf[x],y);
push(graf[y],x);
--m;
}
while (m);
input.close();
m = 1;
x = 0;
do
{
if (!mark[m])
{
++x;
DepthFirstSearch(m);
}
++m;
}
while (m <= n);
std::ofstream output("dfs.out");
output << x << '\n';
output.close();
return 0;
}