Pagini recente » Cod sursa (job #2552199) | Monitorul de evaluare | Clasamentul arhivei de probleme | Cod sursa (job #3166360) | Cod sursa (job #526888)
Cod sursa(job #526888)
#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)
{
int i, comp_conexe = 0;
ofstream g("dfs.out");
readInput();
for (i=0;i<N;i++)
{
if (!visited[i])
{
comp_conexe++;
dfs_visit(i);
}
}
g << comp_conexe;
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 && !visited[it->id])
{
dfs_visit(it->id);
it = it->next;
}
}