Pagini recente » Cod sursa (job #2870477) | Istoria paginii runda/absenta | Istoria paginii runda/rglshw_1./clasament | Cod sursa (job #1751602) | Cod sursa (job #1226520)
#include <iostream>
#include <fstream>
using namespace std;
struct Edge
{
int v;
Edge *next;
};
struct List
{
Edge *begin;
List()
{
begin = NULL;
}
void Insert(int v)
{
if (begin == NULL)
{
begin = new Edge;
begin->v = v;
begin->next = NULL;
}
else
{
Edge *aux = new Edge;
aux->v = v;
aux->next = begin;
begin = aux;
}
}
};
List Graph[100001];
int N, M;
bool Visited[100001];
void Parcurgere(int node)
{
Visited[node] = true;
for (Edge *e = Graph[node].begin; e != NULL; e = e->next)
if (!Visited[e->v])
Parcurgere(e->v);
}
int main()
{
ifstream fin("dfs.in");
fin >> N >> M;
for (int i = 1; i <= M; i++)
{
int a, b;
fin >> a >> b;
Graph[a].Insert(b);
Graph[b].Insert(a);
}
fin.close();
for (int i = 1; i <= N; i++)
Visited[i] = false;
int connectedComponentCount = 0;
for (int i = 1; i <= N; i++)
{
if (!Visited[i])
{
connectedComponentCount++;
Parcurgere(i);
}
}
ofstream fout("dfs.out");
fout << connectedComponentCount;
fout.close();
return 0;
}