Pagini recente » Cod sursa (job #1443906) | Cod sursa (job #1581470) | Cod sursa (job #1593585) | Cod sursa (job #432645) | Cod sursa (job #526897)
Cod sursa(job #526897)
#include <fstream>
using namespace std;
#define NMAX 100000
struct neighbor {
int id;
neighbor* next;
};
int N, M;
bool visited[NMAX];
neighbor* adj_list[NMAX];
void readInput();
void add_edge(int from, int to);
void dfs_visit(int s);
int main(void)
{
ofstream g("dfs.out");
readInput();
int comp_conexe = 0;
for (int i=0;i<N;i++)
{
if (!visited[i])
{
comp_conexe++;
dfs_visit(i);
}
}
g << comp_conexe << "\n";
g.close();
return 0;
}
void readInput()
{
int from, to;
ifstream f("dfs.in");
f >> N >> M;
for (int i=0;i<M;i++)
{
f >> from >> to;
neighbor* x = new neighbor;
x->id = to-1;
x->next = adj_list[from-1];
adj_list[from-1] = x;
x = new neighbor;
x->id = from-1;
x->next = adj_list[to-1];
adj_list[to-1] = x;
}
f.close();
}
void dfs_visit(int s)
{
visited[s] = true;
neighbor* it = adj_list[s];
while (it != NULL)
{
if (!visited[it->id])
{
dfs_visit(it->id);
}
it = it->next;
}
}