Pagini recente » Cod sursa (job #2439193) | Cod sursa (job #2859590) | Cod sursa (job #529223) | Cod sursa (job #2714450) | Cod sursa (job #526893)
Cod sursa(job #526893)
#include <fstream>
#include <queue>
using namespace std;
#define NMAX 100000
struct neighbor {
int id;
neighbor* next;
};
int N, M;
bool visited[NMAX];
neighbor* adj_list[NMAX];
ofstream g("dfs.out");
void readInput();
void BFS(int s);
int main(void)
{
readInput();
int comp_conexe = 0;
for (int i=0;i<N;i++)
{
if (!visited[i])
{
comp_conexe++;
BFS(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] = x;
}
f.close();
}
void BFS(int s)
{
queue<int> Q;
visited[s] = true;
Q.push(s);
while (!Q.empty())
{
int x = Q.front();
Q.pop();
neighbor* it = adj_list[x];
while (it != NULL)
{
if (!visited[it->id])
{
visited[it->id] = true;
Q.push(it->id);
}
it = it->next;
}
}
}